<html>
    <head>
    <link rel="stylesheet" href="lmm.css" type="text/css" />
    </head>
<body class="lmm">
<!-- This file is part of the Lisp Machine Manual.  -*-Text-*- -->
<!-- Function Description: Conses and List Manipulation -->
<!-- NLEFT omitted. -->
<!-- Should this discuss the use of locatives yet, or should that be confined to a section? -->
<p class='cindent'><!-- "conses" -->
<p class='cindent'><!-- "lists" -->
<div class='chapter' id='7'>7. Manipulating List Structure</div><div class='section' id='7.1'>7.1 Conses</div>
<div class='defun' id='car'>
  <font class='exdent'>
    <font class='funcname'>car </font>
    <font class='italic' color='purple'>x</font>
  </font><br>
Returns the <!-- open: 1, close: 0 --><font class="italic">car</font><!-- open: 1, close: 1 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 2, close: 1 --><font class="italic">x</font><!-- open: 2, close: 2 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(car '(a b c)) =&gt; a
</pre>
</div>

<div class='defun' id='cdr'>
  <font class='exdent'>
    <font class='funcname'>cdr </font>
    <font class='italic' color='purple'>x</font>
  </font><br>
Returns the <!-- open: 3, close: 2 --><font class="italic">cdr</font><!-- open: 3, close: 3 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 4, close: 3 --><font class="italic">x</font><!-- open: 4, close: 4 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(cdr '(a b c)) =&gt; (b c)
</pre>
</div>

	Officially <!-- open: 5, close: 4 --><font class="lisp">car</font><!-- open: 5, close: 5 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 6, close: 5 --><font class="lisp">cdr</font><!-- open: 6, close: 6 --> <!-- MATCHED MATCHED MATCHED --> are only applicable to conses and locatives.
However, as a matter of convenience, a degree of control is provided
over the action taken when there is an attempt to apply one of them to
a symbol or a number.  There are four mode-switches known as the
<!-- open: 7, close: 6 --><font class="italic">car-number mode, cdr-number mode, car-symbol mode,</font><!-- open: 7, close: 7 --> <!-- MATCHED MATCHED MATCHED --> and
<!-- open: 8, close: 7 --><font class="italic">cdr-symbol mode</font><!-- open: 8, close: 8 --> <!-- MATCHED MATCHED MATCHED -->.  Here are the meanings of the values of these
mode switches: 

<table>
<tr valign='top'>
<td><font class='lisp'> car-number = 0</font></td><td><!-- open: 9, close: 8 --><font class="italic">car</font><!-- open: 9, close: 9 --> <!-- MATCHED MATCHED MATCHED --> of a number is an error. This is the default.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> car-number = 1</font></td><td><!-- open: 10, close: 9 --><font class="italic">car</font><!-- open: 10, close: 10 --> <!-- MATCHED MATCHED MATCHED --> of a number is <!-- open: 11, close: 10 --><font class="lisp">nil</font><!-- open: 11, close: 11 --> <!-- MATCHED MATCHED MATCHED -->.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-number = 0</font></td><td><!-- open: 12, close: 11 --><font class="italic">cdr</font><!-- open: 12, close: 12 --> <!-- MATCHED MATCHED MATCHED --> of a number is an error. This is the default.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-number = 1</font></td><td><!-- open: 13, close: 12 --><font class="italic">cdr</font><!-- open: 13, close: 13 --> <!-- MATCHED MATCHED MATCHED --> of a number is <!-- open: 14, close: 13 --><font class="lisp">nil</font><!-- open: 14, close: 14 --> <!-- MATCHED MATCHED MATCHED -->.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> car-symbol = 0</font></td><td><!-- open: 15, close: 14 --><font class="italic">car</font><!-- open: 15, close: 15 --> <!-- MATCHED MATCHED MATCHED --> of a symbol is an error.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> car-symbol = 1</font></td><td><!-- open: 16, close: 15 --><font class="italic">car</font><!-- open: 16, close: 16 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 17, close: 16 --><font class="lisp">nil</font><!-- open: 17, close: 17 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 18, close: 17 --><font class="lisp">nil</font><!-- open: 18, close: 18 --> <!-- MATCHED MATCHED MATCHED -->, but the <!-- open: 19, close: 18 --><font class="italic">car</font><!-- open: 19, close: 19 --> <!-- MATCHED MATCHED MATCHED --> of any other
symbol is an error.  This is the default.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> car-symbol = 2</font></td><td><!-- open: 20, close: 19 --><font class="italic">car</font><!-- open: 20, close: 20 --> <!-- MATCHED MATCHED MATCHED --> of any symbol is <!-- open: 21, close: 20 --><font class="lisp">nil</font><!-- open: 21, close: 21 --> <!-- MATCHED MATCHED MATCHED -->.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> car-symbol = 3</font></td><td><!-- open: 22, close: 21 --><font class="italic">car</font><!-- open: 22, close: 22 --> <!-- MATCHED MATCHED MATCHED --> of a symbol is its print-name.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-symbol = 0</font></td><td><!-- open: 23, close: 22 --><font class="italic">cdr</font><!-- open: 23, close: 23 --> <!-- MATCHED MATCHED MATCHED --> of a symbol is an error.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-symbol = 1</font></td><td><!-- open: 24, close: 23 --><font class="italic">cdr</font><!-- open: 24, close: 24 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 25, close: 24 --><font class="lisp">nil</font><!-- open: 25, close: 25 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 26, close: 25 --><font class="lisp">nil</font><!-- open: 26, close: 26 --> <!-- MATCHED MATCHED MATCHED -->, but the <!-- open: 27, close: 26 --><font class="italic">cdr</font><!-- open: 27, close: 27 --> <!-- MATCHED MATCHED MATCHED --> of any other
symbol is an error.  This is the default.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-symbol = 2</font></td><td><!-- open: 28, close: 27 --><font class="italic">cdr</font><!-- open: 28, close: 28 --> <!-- MATCHED MATCHED MATCHED --> of any symbol is <!-- open: 29, close: 28 --><font class="lisp">nil</font><!-- open: 29, close: 29 --> <!-- MATCHED MATCHED MATCHED -->.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> cdr-symbol = 3</font></td><td><!-- open: 30, close: 29 --><font class="italic">cdr</font><!-- open: 30, close: 30 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 31, close: 30 --><font class="lisp">nil</font><!-- open: 31, close: 31 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 32, close: 31 --><font class="lisp">nil</font><!-- open: 32, close: 32 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 33, close: 32 --><font class="italic">cdr</font><!-- open: 33, close: 33 --> <!-- MATCHED MATCHED MATCHED --> of
any other symbol is its property list.
</td></tr><!-- item_ --></table><!-- end table -->


The values of the mode switches can be altered with the function <!-- open: 34, close: 33 --><font class="lisp">set-error-mode</font><!-- open: 34, close: 34 --> <!-- MATCHED MATCHED MATCHED -->
(see <font color='red'>LINK:(</font>set-error-mode-fun)).
'findex "set-error-mode"
They are stored as byte fields in the special variable <!-- open: 35, close: 34 --><font class="lisp">%m-flags</font><!-- open: 35, close: 35 --> <!-- MATCHED MATCHED MATCHED -->.
'vindex "%m-flags"
The reason that the two <!-- open: 36, close: 35 --><font class="italic">symbol</font><!-- open: 36, close: 36 --> <!-- MATCHED MATCHED MATCHED --> modes default in that fashion is
to allow programs to <!-- open: 37, close: 36 --><font class="lisp">car</font><!-- open: 37, close: 37 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 38, close: 37 --><font class="lisp">cdr</font><!-- open: 38, close: 38 --> <!-- MATCHED MATCHED MATCHED --> off the ends of lists without
having to check, which is sometimes useful.  A few system functions depend
on <!-- open: 39, close: 38 --><font class="lisp">car</font><!-- open: 39, close: 39 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 40, close: 39 --><font class="lisp">cdr</font><!-- open: 40, close: 40 --> <!-- MATCHED MATCHED MATCHED --> of <!-- open: 41, close: 40 --><font class="lisp">nil</font><!-- open: 41, close: 41 --> <!-- MATCHED MATCHED MATCHED --> being <!-- open: 42, close: 41 --><font class="lisp">nil</font><!-- open: 42, close: 42 --> <!-- MATCHED MATCHED MATCHED -->, although they
hadn't ought to, so things may break if you change these modes.

The value of 3 for the <!-- open: 43, close: 42 --><font class="italic">symbol</font><!-- open: 43, close: 43 --> <!-- MATCHED MATCHED MATCHED --> modes
exists for compatibility with ancient versions of Maclisp, and should not be used for
any other reasons.  (The appropriate functions are <!-- open: 44, close: 43 --><font class="lisp">get-pname</font><!-- open: 44, close: 44 --> <!-- MATCHED MATCHED MATCHED --> 
(see <font color='red'>LINK:(</font>get-pname-fun)) and <!-- open: 45, close: 44 --><font class="lisp">plist</font><!-- open: 45, close: 45 --> <!-- MATCHED MATCHED MATCHED --> (see <font color='red'>LINK:(</font>plist-fun)).)
'findex "get-pname"
'findex "plist"
Note: unlike Maclisp, the values of the symbols <!-- open: 46, close: 45 --><font class="lisp">car</font><!-- open: 46, close: 46 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 47, close: 46 --><font class="lisp">cdr</font><!-- open: 47, close: 47 --> <!-- MATCHED MATCHED MATCHED --> are not
used; the various mode switches above serve their purpose.
'vindex "car"
'vindex "cdr"
Also unlike Maclisp, this error checking is always done, even in compiled code,
regardless of the value of <!-- open: 48, close: 47 --><font class="lisp">*rset</font><!-- open: 48, close: 48 --> <!-- MATCHED MATCHED MATCHED -->.
'vindex "*rset"

<div class='defun' id='c...r'>
  <font class='exdent'>
    <font class='funcname'>c...r </font>
    <font class='italic' color='purple'>x</font>
  </font><br>
<p id='caaaar'><p id='caaadr'><p id='caaar'><p id='caadar'><p id='caaddr'><p id='caadr'><p id='caar'><p id='cadaar'><p id='cadadr'><p id='cadar'><p id='caddar'><p id='cadddr'><p id='caddr'><p id='cadr'><p id='cdaaar'><p id='cdaadr'><p id='cdaar'><p id='cdadar'><p id='cdaddr'><p id='cdadr'><p id='cdar'><p id='cddaar'><p id='cddadr'><p id='cddar'><p id='cdddar'><p id='cddddr'><p id='cdddr'><p id='cddr'>All of the compositions of up to four <!-- open: 49, close: 48 --><font class="italic">car</font><!-- open: 49, close: 49 --> <!-- MATCHED MATCHED MATCHED -->'s and <!-- open: 50, close: 49 --><font class="italic">cdr</font><!-- open: 50, close: 50 --> <!-- MATCHED MATCHED MATCHED -->'s are defined as
functions in their own right.  The names of these functions begin with "<!-- open: 51, close: 50 --><font class="lisp">c</font><!-- open: 51, close: 51 --> <!-- MATCHED MATCHED MATCHED -->" and end
with "<!-- open: 52, close: 51 --><font class="lisp">r</font><!-- open: 52, close: 52 --> <!-- MATCHED MATCHED MATCHED -->", and in between is a sequence of "<!-- open: 53, close: 52 --><font class="lisp">a</font><!-- open: 53, close: 53 --> <!-- MATCHED MATCHED MATCHED -->"'s and "<!-- open: 54, close: 53 --><font class="lisp">d</font><!-- open: 54, close: 54 --> <!-- MATCHED MATCHED MATCHED -->"'s corresponding to
the composition performed by the function. 
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(cddadr x) <!-- open: 55, close: 54 --><font class="main">is the same as</font><!-- open: 55, close: 55 --> <!-- MATCHED MATCHED MATCHED --> (cdr (cdr (car (cdr x))))
</pre>
The error checking for these functions is exactly the same as for <!-- open: 56, close: 55 --><font class="lisp">car</font><!-- open: 56, close: 56 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 57, close: 56 --><font class="lisp">cdr</font><!-- open: 57, close: 57 --> <!-- MATCHED MATCHED MATCHED -->
above.
</div>
	
<div class='defun' id='cons'>
  <font class='exdent'>
    <font class='funcname'>cons </font>
    <font class='italic' color='purple'>x y</font>
  </font><br>
<!-- open: 58, close: 57 --><font class="lisp">cons</font><!-- open: 58, close: 58 --> <!-- MATCHED MATCHED MATCHED --> is the primitive function to create a new <!-- open: 59, close: 58 --><font class="italic">cons</font><!-- open: 59, close: 59 --> <!-- MATCHED MATCHED MATCHED -->, whose
<!-- open: 60, close: 59 --><font class="italic">car</font><!-- open: 60, close: 60 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 61, close: 60 --><font class="italic">x</font><!-- open: 61, close: 61 --> <!-- MATCHED MATCHED MATCHED --> and whose <!-- open: 62, close: 61 --><font class="italic">cdr</font><!-- open: 62, close: 62 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 63, close: 62 --><font class="italic">y</font><!-- open: 63, close: 63 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(cons 'a 'b) =&gt; (a . b)
(cons 'a (cons 'b (cons 'c nil))) =&gt; (a b c)
(cons 'a '(b c d)) =&gt; (a b c d)
</pre>
</div>

<div class='defun' id='ncons'>
  <font class='exdent'>
    <font class='funcname'>ncons </font>
    <font class='italic' color='purple'>x</font>
  </font><br>
<!-- open: 64, close: 63 --><font class="lisp">(ncons <!-- open: 65, close: 63 --><font class="italic">x</font><!-- open: 65, close: 64 -->)</font><!-- open: 65, close: 65 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 66, close: 65 --><font class="lisp">(cons <!-- open: 67, close: 65 --><font class="italic">x</font><!-- open: 67, close: 66 --> nil)</font><!-- open: 67, close: 67 --> <!-- MATCHED MATCHED MATCHED -->.
The name of the function is from "nil-cons".
</div>

<div class='defun' id='xcons'>
  <font class='exdent'>
    <font class='funcname'>xcons </font>
    <font class='italic' color='purple'>x y</font>
  </font><br>
<!-- open: 68, close: 67 --><font class="lisp">xcons</font><!-- open: 68, close: 68 --> <!-- MATCHED MATCHED MATCHED --> ("exchanged cons") is like <!-- open: 69, close: 68 --><font class="lisp">cons</font><!-- open: 69, close: 69 --> <!-- MATCHED MATCHED MATCHED --> except that the order of
the arguments is reversed.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(xcons 'a 'b) =&gt; (b . a)
</pre>
	There are two reasons this exists: one is that you might want the arguments
to <!-- open: 70, close: 69 --><font class="lisp">cons</font><!-- open: 70, close: 70 --> <!-- MATCHED MATCHED MATCHED --> evaluated in the other order, and the other is that the compiler
might convert calls to <!-- open: 71, close: 70 --><font class="lisp">cons</font><!-- open: 71, close: 71 --> <!-- MATCHED MATCHED MATCHED --> into calls to <!-- open: 72, close: 71 --><font class="lisp">xcons</font><!-- open: 72, close: 72 --> <!-- MATCHED MATCHED MATCHED --> for efficiency.  In fact,
it doesn't.
</div>

<div class='defun' id='cons-in-area'>
  <font class='exdent'>
    <font class='funcname'>cons-in-area </font>
    <font class='italic' color='purple'>x y area-number</font>
  </font><br>
<p class='cindent'><!-- "area" -->
This function creates a <!-- open: 73, close: 72 --><font class="italic">cons</font><!-- open: 73, close: 73 --> <!-- MATCHED MATCHED MATCHED --> in a specific <!-- open: 74, close: 73 --><font class="italic">area</font><!-- open: 74, close: 74 --> <!-- MATCHED MATCHED MATCHED -->.  (<!-- open: 75, close: 74 --><font class="italic">Areas</font><!-- open: 75, close: 75 --> <!-- MATCHED MATCHED MATCHED -->
are an advanced feature of storage management; if you aren't interested in them,
you can safely skip all this stuff).  The first two arguments are the same as the
two arguments to <!-- open: 76, close: 75 --><font class="lisp">cons</font><!-- open: 76, close: 76 --> <!-- MATCHED MATCHED MATCHED -->,  and the third is the number of the area in which
to create the <!-- open: 77, close: 76 --><font class="italic">cons</font><!-- open: 77, close: 77 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(cons-in-area 'a 'b my-area) =&gt; (a . b)
</pre>
</div>

<div class='defun' id='ncons-in-area'>
  <font class='exdent'>
    <font class='funcname'>ncons-in-area </font>
    <font class='italic' color='purple'>x area-number</font>
  </font><br>
<!-- open: 78, close: 77 --><font class="lisp">(ncons-in-area <!-- open: 79, close: 77 --><font class="italic">x area-number</font><!-- open: 79, close: 78 -->)</font><!-- open: 79, close: 79 --> <!-- MATCHED MATCHED MATCHED --> = <!-- open: 80, close: 79 --><font class="lisp">(cons-in-area <!-- open: 81, close: 79 --><font class="italic">x</font><!-- open: 81, close: 80 --> nil <!-- open: 82, close: 80 --><font class="italic">area-number</font><!-- open: 82, close: 81 -->)</font><!-- open: 82, close: 82 --> <!-- MATCHED MATCHED MATCHED -->
</div>

<div class='defun' id='xcons-in-area'>
  <font class='exdent'>
    <font class='funcname'>xcons-in-area </font>
    <font class='italic' color='purple'>x y area-number</font>
  </font><br>
<!-- open: 83, close: 82 --><font class="lisp">(xcons-in-area <!-- open: 84, close: 82 --><font class="italic">x y area-number</font><!-- open: 84, close: 83 -->) = (cons-in-area <!-- open: 85, close: 83 --><font class="italic">y x area-number</font><!-- open: 85, close: 84 -->)</font><!-- open: 85, close: 85 --> <!-- MATCHED MATCHED MATCHED -->
</div>

	The backquote reader macro facility is also generally useful
for creating list structure, especially mostly-constant list structure,
or forms constructed by plugging variables into a template.
It is documented in the chapter on Macros, see <font color='red'>LINK:(</font>macro).

<div class='defun' id='car-location'>
  <font class='exdent'>
    <font class='funcname'>car-location </font>
    <font class='italic' color='purple'>cons</font>
  </font><br>
<!-- open: 86, close: 85 --><font class="lisp">car-location</font><!-- open: 86, close: 86 --> <!-- MATCHED MATCHED MATCHED --> returns a locative pointer to the cell containing
the car of <!-- open: 87, close: 86 --><font class="italic">cons</font><!-- open: 87, close: 87 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

Note: there is no <!-- open: 88, close: 87 --><font class="lisp">cdr-location</font><!-- open: 88, close: 88 --> <!-- MATCHED MATCHED MATCHED --> function; it is difficult
because of the cdr-coding scheme.

<div class='section' id='7.2'>7.2 Lists</div><p class='cindent'><!-- "cons vs list" -->
	The following section explains some of the basic functions
provided for dealing with <!-- open: 89, close: 88 --><font class="italic">lists</font><!-- open: 89, close: 89 --> <!-- MATCHED MATCHED MATCHED -->.  There has been some confusion
about the term <!-- open: 90, close: 89 --><font class="italic">list</font><!-- open: 90, close: 90 --> <!-- MATCHED MATCHED MATCHED --> ever since the beginnings of the language: for
the purposes of the following descriptions, a list is the symbol
<!-- open: 91, close: 90 --><font class="lisp">nil</font><!-- open: 91, close: 91 --> <!-- MATCHED MATCHED MATCHED -->, or a cons whose cdr is a list.  Note well that although we
consider <!-- open: 92, close: 91 --><font class="lisp">nil</font><!-- open: 92, close: 92 --> <!-- MATCHED MATCHED MATCHED --> to be a <!-- open: 93, close: 92 --><font class="italic">list</font><!-- open: 93, close: 93 --> <!-- MATCHED MATCHED MATCHED --> (the list of zero elements), it is a
symbol and not a cons, and the <!-- open: 94, close: 93 --><font class="lisp">listp</font><!-- open: 94, close: 94 --> <!-- MATCHED MATCHED MATCHED --> predicate is not true of it
(but perhaps <!-- open: 95, close: 94 --><font class="lisp">listp</font><!-- open: 95, close: 95 --> <!-- MATCHED MATCHED MATCHED --> will be changed in the future).

<div class='defun' id='last'>
  <font class='exdent'>
    <font class='funcname'>last </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
<!-- open: 96, close: 95 --><font class="lisp">last</font><!-- open: 96, close: 96 --> <!-- MATCHED MATCHED MATCHED --> returns the last cons of <!-- open: 97, close: 96 --><font class="italic">list</font><!-- open: 97, close: 97 --> <!-- MATCHED MATCHED MATCHED -->.  If <!-- open: 98, close: 97 --><font class="italic">list</font><!-- open: 98, close: 98 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 99, close: 98 --><font class="lisp">nil</font><!-- open: 99, close: 99 --> <!-- MATCHED MATCHED MATCHED -->,
it returns <!-- open: 100, close: 99 --><font class="lisp">nil</font><!-- open: 100, close: 100 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq x '(a b c d))
(last x) =&gt; (d)
(rplacd (last x) '(e f))
x =&gt; '(a b c d e f)
</pre>
<!-- open: 101, close: 100 --><font class="lisp">last</font><!-- open: 101, close: 101 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun last (x)
    (cond ((atom x) x)
          ((atom (cdr x)) x)
          ((last (cdr x))) ))
</pre>
</div>

<div class='defun' id='length'>
  <font class='exdent'>
    <font class='funcname'>length </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
<!-- open: 102, close: 101 --><font class="lisp">length</font><!-- open: 102, close: 102 --> <!-- MATCHED MATCHED MATCHED --> returns the length of <!-- open: 103, close: 102 --><font class="italic">list</font><!-- open: 103, close: 103 --> <!-- MATCHED MATCHED MATCHED -->.  The length of a list
is the number of top-level conses in it.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(length nil) =&gt; 0
(length '(a b c d)) =&gt; 4
(length '(a (b c) d)) =&gt; 3
</pre>
<!-- open: 104, close: 103 --><font class="lisp">length</font><!-- open: 104, close: 104 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun length (x)
    (cond ((atom x) 0)
          ((1+ (length (cdr x)))) ))
<!-- open: 105, close: 104 --><font class="main">or by:</font><!-- open: 105, close: 105 --> <!-- MATCHED MATCHED MATCHED -->

(defun length (x)
    (do ((n 0 (1+ n))
         (y x (cdr y)))
        ((atom y) n) ))
</pre>
</div>

<div class='defmac' id='first'><font class='exdent'><font class='funcname' id='first'>first</font><font class="italic"> Macro</font></br></font><!-- end font_exdent --></div><div class='defmac id='second''><font class='exdent'><font class='funcname' id='second'>second</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='third''><font class='exdent'><font class='funcname' id='third'>third</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='fourth''><font class='exdent'><font class='funcname' id='fourth'>fourth</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='fifth''><font class='exdent'><font class='funcname' id='fifth'>fifth</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='sixth''><font class='exdent'><font class='funcname' id='sixth'>sixth</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='seventh''><font class='exdent'><font class='funcname' id='seventh'>seventh</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --><pre class='lisp'>
(first x) ==&gt; (car x)
(second x) ==&gt; (cadr x)
(third x) ==&gt; (caddr x)
(fourth x) ==&gt; (cadddr x)
<!-- open: 106, close: 105 --><font class="main">etc.</font><!-- open: 106, close: 106 --> <!-- MATCHED MATCHED MATCHED -->
</pre>
</div>

<div class='defmac' id='rest1'><font class='exdent'><font class='funcname' id='rest1'>rest1</font><font class="italic"> Macro</font></br></font><!-- end font_exdent --></div><div class='defmac id='rest2''><font class='exdent'><font class='funcname' id='rest2'>rest2</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='rest3''><font class='exdent'><font class='funcname' id='rest3'>rest3</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --></div><div class='defmac id='rest4''><font class='exdent'><font class='funcname' id='rest4'>rest4</font><font class="italic"> Macro</font><br></font><!-- end font_exdent --><pre class='lisp'>
(rest1 x) ==&gt; (cdr x)
(rest2 x) ==&gt; (cddr x)
(rest3 x) ==&gt; (cdddr x)
(rest4 x) ==&gt; (cddddr x)
</pre>
</div>

<div class='defun' id='nth'>
  <font class='exdent'>
    <font class='funcname'>nth </font>
    <font class='italic' color='purple'>n list</font>
  </font><br>
<!-- open: 107, close: 106 --><font class="lisp">(nth <!-- open: 108, close: 106 --><font class="italic">n list</font><!-- open: 108, close: 107 -->)</font><!-- open: 108, close: 108 --> <!-- MATCHED MATCHED MATCHED --> returns the <!-- open: 109, close: 108 --><font class="italic">n</font><!-- open: 109, close: 109 --> <!-- MATCHED MATCHED MATCHED -->'th element of <!-- open: 110, close: 109 --><font class="italic">list</font><!-- open: 110, close: 110 --> <!-- MATCHED MATCHED MATCHED -->, where
the zeroth element is the <!-- open: 111, close: 110 --><font class="italic">car</font><!-- open: 111, close: 111 --> <!-- MATCHED MATCHED MATCHED --> of the list.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(nth 1 '(foo bar gack)) =&gt; bar
(nth 3 '(foo bar gack)) =&gt; nil
</pre>
Note: this is not the same as the InterLisp function called <!-- open: 112, close: 111 --><font class="lisp">nth</font><!-- open: 112, close: 112 --> <!-- MATCHED MATCHED MATCHED -->,
which is similar to but not exactly the same as the Lisp Machine function
<!-- open: 113, close: 112 --><font class="lisp">nthcdr</font><!-- open: 113, close: 113 --> <!-- MATCHED MATCHED MATCHED -->.
Also, some people have used macros and functions called <!-- open: 114, close: 113 --><font class="lisp">nth</font><!-- open: 114, close: 114 --> <!-- MATCHED MATCHED MATCHED --> of their own in
their Maclisp programs, which may not work the same way; be careful.

<!-- open: 115, close: 114 --><font class="lisp">nth</font><!-- open: 115, close: 115 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun nth (n list)
  (do ((i n (1- i))
       (l list (cdr l)))
      ((zerop i) (car l))))
</pre>
</div>

<div class='defun' id='nthcdr'>
  <font class='exdent'>
    <font class='funcname'>nthcdr </font>
    <font class='italic' color='purple'>n list</font>
  </font><br>
<!-- open: 116, close: 115 --><font class="lisp">(nthcdr <!-- open: 117, close: 115 --><font class="italic">n list</font><!-- open: 117, close: 116 -->)</font><!-- open: 117, close: 117 --> <!-- MATCHED MATCHED MATCHED --> <!-- open: 118, close: 117 --><font class="italic">cdr</font><!-- open: 118, close: 118 --> <!-- MATCHED MATCHED MATCHED -->s <!-- open: 119, close: 118 --><font class="italic">list</font><!-- open: 119, close: 119 --> <!-- MATCHED MATCHED MATCHED --> <!-- open: 120, close: 119 --><font class="italic">n</font><!-- open: 120, close: 120 --> <!-- MATCHED MATCHED MATCHED --> times,
and returns the result.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(nthcdr 0 '(a b c)) =&gt; (a b c)
(nthcdr 2 '(a b c)) =&gt; (c)
</pre>
In other words, it returns the <!-- open: 121, close: 120 --><font class="italic">n</font><!-- open: 121, close: 121 --> <!-- MATCHED MATCHED MATCHED -->'th <!-- open: 122, close: 121 --><font class="italic">cdr</font><!-- open: 122, close: 122 --> <!-- MATCHED MATCHED MATCHED --> of the list.
This is the similar to InterLisp's function <!-- open: 123, close: 122 --><font class="lisp">nth</font><!-- open: 123, close: 123 --> <!-- MATCHED MATCHED MATCHED -->, except that the
InterLisp function is one-based instead of zero-based; see the
InterLisp manual for details.
<!-- open: 124, close: 123 --><font class="lisp">nthcdr</font><!-- open: 124, close: 124 --> <!-- MATCHED MATCHED MATCHED --> is defined by:
<pre class='lisp'>
(defun nthcdr (n list)
    (do ((i 0 (1+ i))
	 (list list (cdr list)))
	((= i n) list)))
</pre>
</div>

<div class='defun' id='list'>
  <font class='exdent'>
    <font class='funcname'>list </font>
    <font class='italic' color='purple'>&rest args</font>
  </font><br>
<!-- open: 125, close: 124 --><font class="lisp">list</font><!-- open: 125, close: 125 --> <!-- MATCHED MATCHED MATCHED --> constructs and returns a list of its arguments.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(list 3 4 'a (car '(b . c)) (+ 6 -2)) =&gt; (3 4 a b 4)
</pre>
<!-- open: 126, close: 125 --><font class="lisp">list</font><!-- open: 126, close: 126 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun list (&amp;rest args)
    (let ((list (make-list default-cons-area (length args))))
      (do ((l list (cdr l))
	   (a args (cdr a)))
	  ((null a) list)
	(rplaca l (car a)))))
</pre>
</div>

<div class='defun' id='list*'>
  <font class='exdent'>
    <font class='funcname'>list* </font>
    <font class='italic' color='purple'>&rest args</font>
  </font><br>
<!-- open: 127, close: 126 --><font class="lisp">list*</font><!-- open: 127, close: 127 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 128, close: 127 --><font class="lisp">list</font><!-- open: 128, close: 128 --> <!-- MATCHED MATCHED MATCHED --> except that the last <!-- open: 129, close: 128 --><font class="italic">cons</font><!-- open: 129, close: 129 --> <!-- MATCHED MATCHED MATCHED -->
of the constructed list is "dotted".  It must be given at least
two arguments.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(list* 'a 'b 'c 'd) =&gt; (a b c . d)
<!-- open: 130, close: 129 --><font class="main">This is like</font><!-- open: 130, close: 130 --> <!-- MATCHED MATCHED MATCHED -->
(cons 'a (cons 'b (cons 'c 'd)))
</pre>
</div>

<div class='defun' id='list-in-area'>
  <font class='exdent'>
    <font class='funcname'>list-in-area </font>
    <font class='italic' color='purple'>area-number &rest args</font>
  </font><br>
<!-- open: 131, close: 130 --><font class="lisp">list-in-area</font><!-- open: 131, close: 131 --> <!-- MATCHED MATCHED MATCHED --> is exactly the same as <!-- open: 132, close: 131 --><font class="lisp">list</font><!-- open: 132, close: 132 --> <!-- MATCHED MATCHED MATCHED --> except that it takes
an extra argument, an area number, and creates the list in that area.
</div>

<div class='defun' id='make-list'>
  <font class='exdent'>
    <font class='funcname'>make-list </font>
    <font class='italic' color='purple'>area size</font>
  </font><br>
This creates and returns a list containing <!-- open: 133, close: 132 --><font class="italic">size</font><!-- open: 133, close: 133 --> <!-- MATCHED MATCHED MATCHED --> elements, each
of which is <!-- open: 134, close: 133 --><font class="lisp">nil</font><!-- open: 134, close: 134 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 135, close: 134 --><font class="italic">size</font><!-- open: 135, close: 135 --> <!-- MATCHED MATCHED MATCHED --> should be a fixnum.  The list
is allocated in the area specified; if you are not using areas in any special
way, just use the value of the symbol <!-- open: 136, close: 135 --><font class="lisp">default-cons-area</font><!-- open: 136, close: 136 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(make-list default-cons-area 3) =&gt; (nil nil nil)
</pre>
Of course, this function is not usually used when the value of the second argument
is a constant; if you want a list of three <!-- open: 137, close: 136 --><font class="lisp">nil</font><!-- open: 137, close: 137 --> <!-- MATCHED MATCHED MATCHED -->s, it is easy enough
to type <!-- open: 138, close: 137 --><font class="lisp">(nil nil nil)</font><!-- open: 138, close: 138 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 139, close: 138 --><font class="lisp">make-list</font><!-- open: 139, close: 139 --> <!-- MATCHED MATCHED MATCHED --> is used when the number
of elements is to be computed while the program is being run.

<!-- open: 140, close: 139 --><font class="lisp">make-list</font><!-- open: 140, close: 140 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 141, close: 140 --><font class="lisp">cons</font><!-- open: 141, close: 141 --> <!-- MATCHED MATCHED MATCHED --> are the two primitive list-creation functions
which all the other functions call.  The difference is that <!-- open: 142, close: 141 --><font class="lisp">make-list</font><!-- open: 142, close: 142 --> <!-- MATCHED MATCHED MATCHED -->
creates a <!-- open: 143, close: 142 --><font class="italic">cdr-coded</font><!-- open: 143, close: 143 --> <!-- MATCHED MATCHED MATCHED --> list (see <a href='fd_con.html#cdr-code'>this link</a>).
</div>

<div class='defun' id='circular-list'>
  <font class='exdent'>
    <font class='funcname'>circular-list </font>
    <font class='italic' color='purple'>&rest args</font>
  </font><br>
<!-- open: 144, close: 143 --><font class="lisp">circular-list</font><!-- open: 144, close: 144 --> <!-- MATCHED MATCHED MATCHED --> constructs a circular list whose elements are <!-- open: 145, close: 144 --><font class="lisp">args</font><!-- open: 145, close: 145 --> <!-- MATCHED MATCHED MATCHED -->, repeated
infinitely.  <!-- open: 146, close: 145 --><font class="lisp">circular-list</font><!-- open: 146, close: 146 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 147, close: 146 --><font class="lisp">list</font><!-- open: 147, close: 147 --> <!-- MATCHED MATCHED MATCHED --> except that the list itself
is used as the last cdr, instead of <!-- open: 148, close: 147 --><font class="lisp">nil</font><!-- open: 148, close: 148 --> <!-- MATCHED MATCHED MATCHED -->.
<!-- open: 149, close: 148 --><font class="lisp">circular-list</font><!-- open: 149, close: 149 --> <!-- MATCHED MATCHED MATCHED --> is especially useful with <!-- open: 150, close: 149 --><font class="lisp">mapcar</font><!-- open: 150, close: 150 --> <!-- MATCHED MATCHED MATCHED -->, as in the expression
<pre class='lisp'>
(mapcar (function +) foo (circular-list 5))
</pre>
which adds each element of <!-- open: 151, close: 150 --><font class="lisp">foo</font><!-- open: 151, close: 151 --> <!-- MATCHED MATCHED MATCHED --> to 5.
</div>

<div class='defun' id='append'>
  <font class='exdent'>
    <font class='funcname'>append </font>
    <font class='italic' color='purple'>&rest lists</font>
  </font><br>
The arguments to <!-- open: 152, close: 151 --><font class="lisp">append</font><!-- open: 152, close: 152 --> <!-- MATCHED MATCHED MATCHED --> are lists.  The result is a list which is the
concatenation of the arguments.
The arguments are not changed (cf. <!-- open: 153, close: 152 --><font class="lisp">nconc</font><!-- open: 153, close: 153 --> <!-- MATCHED MATCHED MATCHED -->).
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(append '(a b c) '(d e f) nil '(g)) =&gt; (a b c d e f g)
</pre>
Note that <!-- open: 154, close: 153 --><font class="lisp">append</font><!-- open: 154, close: 154 --> <!-- MATCHED MATCHED MATCHED --> copies the top-level list structure of each of its
arguments except the last.  Thus, to copy
a list but not its elements, use <!-- open: 155, close: 154 --><font class="lisp">(append <!-- open: 156, close: 154 --><font class="italic">x</font><!-- open: 156, close: 155 --> nil)</font><!-- open: 156, close: 156 --> <!-- MATCHED MATCHED MATCHED -->.
The <!-- open: 157, close: 156 --><font class="lisp">copylist</font><!-- open: 157, close: 157 --> <!-- MATCHED MATCHED MATCHED --> function is equivalent.

A version of <!-- open: 158, close: 157 --><font class="lisp">append</font><!-- open: 158, close: 158 --> <!-- MATCHED MATCHED MATCHED --> which only accepts two arguments could have been defined by:
<pre class='lisp'>
(defun append2 (x y)
    (cond ((null x) y)
          ((cons (car x) (append2 (cdr x) y)) )))
</pre>

The generalization to any number of arguments could then be made:
<pre class='lisp'>
(defun append (&amp;rest args)
    (and args (append2 (car args)
		       (apply (function append) (cdr args)))))
</pre>

These definitions do not express the full functionality of <!-- open: 159, close: 158 --><font class="lisp">append</font><!-- open: 159, close: 159 --> <!-- MATCHED MATCHED MATCHED -->; the
real definition minimizes storage utilization by cdr-coding the list it produces,
using <!-- open: 160, close: 159 --><font class="italic">cdr-next</font><!-- open: 160, close: 160 --> <!-- MATCHED MATCHED MATCHED --> except at the end where a full node is used to link to
the last argument, unless the last argument was <!-- open: 161, close: 160 --><font class="lisp">nil</font><!-- open: 161, close: 161 --> <!-- MATCHED MATCHED MATCHED --> in which case
<!-- open: 162, close: 161 --><font class="italic">cdr-nil</font><!-- open: 162, close: 162 --> <!-- MATCHED MATCHED MATCHED --> is used.
</div>

<div class='defun' id='copylist'>
  <font class='exdent'>
    <font class='funcname'>copylist </font>
    <font class='italic' color='purple'>list &optional area</font>
  </font><br>
Returns a list which is <!-- open: 163, close: 162 --><font class="lisp">equal</font><!-- open: 163, close: 163 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 164, close: 163 --><font class="italic">list</font><!-- open: 164, close: 164 --> <!-- MATCHED MATCHED MATCHED -->, but not <!-- open: 165, close: 164 --><font class="lisp">eq</font><!-- open: 165, close: 165 --> <!-- MATCHED MATCHED MATCHED -->.
Only the top level of list-structure is copied, i.e. <!-- open: 166, close: 165 --><font class="lisp">copylist</font><!-- open: 166, close: 166 --> <!-- MATCHED MATCHED MATCHED -->
copies in the <!-- open: 167, close: 166 --><font class="lisp">cdr</font><!-- open: 167, close: 167 --> <!-- MATCHED MATCHED MATCHED --> direction but not in the <!-- open: 168, close: 167 --><font class="lisp">car</font><!-- open: 168, close: 168 --> <!-- MATCHED MATCHED MATCHED --> direction.
The returned list is fully cdr-coded to minimize storage.
If the list is "dotted", that is, <!-- open: 169, close: 168 --><font class="lisp">(cdr (last <!-- open: 170, close: 168 --><font class="italic">list</font><!-- open: 170, close: 169 -->))</font><!-- open: 170, close: 170 --> <!-- MATCHED MATCHED MATCHED -->
is a non-<!-- open: 171, close: 170 --><font class="lisp">nil</font><!-- open: 171, close: 171 --> <!-- MATCHED MATCHED MATCHED --> atom, this will be true of the returned list also.
You may optionally specify the area in which to create the new copy.
</div>

<div class='defun' id='copylist*'>
  <font class='exdent'>
    <font class='funcname'>copylist* </font>
    <font class='italic' color='purple'>list &optional area</font>
  </font><br>
This is the same as <!-- open: 172, close: 171 --><font class="lisp">copylist</font><!-- open: 172, close: 172 --> <!-- MATCHED MATCHED MATCHED --> except that the last cons of the
resulting list is never cdr-coded.  This makes for increased efficiency
if you <!-- open: 173, close: 172 --><font class="lisp">nconc</font><!-- open: 173, close: 173 --> <!-- MATCHED MATCHED MATCHED --> something onto the list later.
</div>

<div class='defun' id='copyalist'>
  <font class='exdent'>
    <font class='funcname'>copyalist </font>
    <font class='italic' color='purple'>list &optional area</font>
  </font><br>
<!-- open: 174, close: 173 --><font class="lisp">copyalist</font><!-- open: 174, close: 174 --> <!-- MATCHED MATCHED MATCHED --> is for copying association lists.  The top level of
list structure of <!-- open: 175, close: 174 --><font class="italic">list</font><!-- open: 175, close: 175 --> <!-- MATCHED MATCHED MATCHED --> is copied, just as <!-- open: 176, close: 175 --><font class="lisp">copylist</font><!-- open: 176, close: 176 --> <!-- MATCHED MATCHED MATCHED --> does.
In addition, each element of <!-- open: 177, close: 176 --><font class="italic">list</font><!-- open: 177, close: 177 --> <!-- MATCHED MATCHED MATCHED --> which is a cons is replaced
in the copy by a new cons with the same car and cdr.
You may optionally specify the area in which to create the new copy.
</div>

<div class='defun' id='reverse'>
  <font class='exdent'>
    <font class='funcname'>reverse </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
<!-- open: 178, close: 177 --><font class="lisp">reverse</font><!-- open: 178, close: 178 --> <!-- MATCHED MATCHED MATCHED --> creates a new list whose elements
are the elements of <!-- open: 179, close: 178 --><font class="italic">list</font><!-- open: 179, close: 179 --> <!-- MATCHED MATCHED MATCHED --> taken in reverse order.
<!-- open: 180, close: 179 --><font class="lisp">reverse</font><!-- open: 180, close: 180 --> <!-- MATCHED MATCHED MATCHED --> does not modify its argument, unlike <!-- open: 181, close: 180 --><font class="lisp">nreverse</font><!-- open: 181, close: 181 --> <!-- MATCHED MATCHED MATCHED --> which is faster
but does modify its argument.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(reverse '(a b (c d) e)) =&gt; (e (c d) b a)
</pre>
<!-- open: 182, close: 181 --><font class="lisp">reverse</font><!-- open: 182, close: 182 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun reverse (x)
    (do ((l x (cdr l))         ;<!-- open: 183, close: 182 --><font class="main"> scan down argument,</font><!-- open: 183, close: 183 --> <!-- MATCHED MATCHED MATCHED -->
         (r nil                ;<!-- open: 184, close: 183 --><font class="main"> putting each element</font><!-- open: 184, close: 184 --> <!-- MATCHED MATCHED MATCHED -->
            (cons (car l) r))) ;<!-- open: 185, close: 184 --><font class="main"> into list, until</font><!-- open: 185, close: 185 --> <!-- MATCHED MATCHED MATCHED -->
        ((null l) r)))         ;<!-- open: 186, close: 185 --><font class="main"> no more elements.</font><!-- open: 186, close: 186 --> <!-- MATCHED MATCHED MATCHED -->
</pre>
</div>

<div class='defun' id='nconc'>
  <font class='exdent'>
    <font class='funcname'>nconc </font>
    <font class='italic' color='purple'>&rest lists</font>
  </font><br>
<!-- open: 187, close: 186 --><font class="lisp">nconc</font><!-- open: 187, close: 187 --> <!-- MATCHED MATCHED MATCHED --> takes lists as arguments.  It returns a list which is the arguments
concatenated together.  The arguments are changed, rather than copied.
(cf. <!-- open: 188, close: 187 --><font class="lisp">append</font><!-- open: 188, close: 188 --> <!-- MATCHED MATCHED MATCHED -->, <font color='red'>LINK:(</font>append-fun))
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq x '(a b c))
(setq y '(d e f))
(nconc x y) =&gt; (a b c d e f)
x =&gt; (a b c d e f)
</pre>
Note that the value of x is now different, since its last cons has been <!-- open: 189, close: 188 --><font class="lisp">rplacd</font><!-- open: 189, close: 189 --> <!-- MATCHED MATCHED MATCHED -->'d to
the value of <!-- open: 190, close: 189 --><font class="lisp">y</font><!-- open: 190, close: 190 --> <!-- MATCHED MATCHED MATCHED -->.
If the nconc form is evaluated again, it would yield a piece of "circular" list
structure, whose printed representation would be
<!-- open: 191, close: 190 --><font class="lisp">(a b c d e f d e f d e f ...)</font><!-- open: 191, close: 191 --> <!-- MATCHED MATCHED MATCHED -->, repeating forever.

<!-- open: 192, close: 191 --><font class="lisp">nconc</font><!-- open: 192, close: 192 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun nconc (x y)		 ;<!-- open: 193, close: 192 --><font class="main">for simplicity, this definition</font><!-- open: 193, close: 193 --> <!-- MATCHED MATCHED MATCHED -->
    (cond ((null x) y)		 ;<!-- open: 194, close: 193 --><font class="main">only works for 2 arguments.</font><!-- open: 194, close: 194 --> <!-- MATCHED MATCHED MATCHED -->
          (t (rplacd (last x) y) ;<!-- open: 195, close: 194 --><font class="main">hook <!-- open: 196, close: 194 --><font class="lisp">y</font><!-- open: 196, close: 195 --> onto </font><!-- open: 196, close: 196 --> <!-- MATCHED MATCHED MATCHED -->x
              x)))		 ;<!-- open: 197, close: 196 --><font class="main">and return the modified <!-- open: 198, close: 196 --><font class="lisp">x</font><!-- open: 198, close: 197 -->.</font><!-- open: 198, close: 198 --> <!-- MATCHED MATCHED MATCHED -->
</pre>
</div>

<div class='defun' id='nreverse'>
  <font class='exdent'>
    <font class='funcname'>nreverse </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
<!-- open: 199, close: 198 --><font class="lisp">nreverse</font><!-- open: 199, close: 199 --> <!-- MATCHED MATCHED MATCHED --> reverses its argument, which should be a list.  The argument
is destroyed by <!-- open: 200, close: 199 --><font class="lisp">rplacd</font><!-- open: 200, close: 200 --> <!-- MATCHED MATCHED MATCHED -->'s all through the list (cf. <!-- open: 201, close: 200 --><font class="lisp">reverse</font><!-- open: 201, close: 201 --> <!-- MATCHED MATCHED MATCHED -->).
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(nreverse '(a b c)) =&gt; (c b a)
</pre>
<!-- open: 202, close: 201 --><font class="lisp">nreverse</font><!-- open: 202, close: 202 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun nreverse  (x)
    (cond ((null x) nil)
          ((nreverse1 x nil))))

(defun nreverse1 (x y)		;<!-- open: 203, close: 202 --><font class="main">auxiliary function</font><!-- open: 203, close: 203 --> <!-- MATCHED MATCHED MATCHED -->
    (cond ((null (cdr x)) (rplacd x y))
          ((nreverse1 (cdr x) (rplacd x y)))))
          ;;<!-- open: 204, close: 203 --><font class="main"> this last call depends on order of argument evaluation.</font><!-- open: 204, close: 204 --> <!-- MATCHED MATCHED MATCHED -->
</pre>

Currently, <!-- open: 205, close: 204 --><font class="lisp">nreverse</font><!-- open: 205, close: 205 --> <!-- MATCHED MATCHED MATCHED --> does something inefficient with <!-- open: 206, close: 205 --><font class="italic">cdr-coded</font><!-- open: 206, close: 206 --> <!-- MATCHED MATCHED MATCHED -->
lists, however this will be changed.  In the meantime <!-- open: 207, close: 206 --><font class="lisp">reverse</font><!-- open: 207, close: 207 --> <!-- MATCHED MATCHED MATCHED --> might
be preferable in some cases.
</div>

<div class='defun' id='nreconc'>
  <font class='exdent'>
    <font class='funcname'>nreconc </font>
    <font class='italic' color='purple'>x y</font>
  </font><br>
<!-- open: 208, close: 207 --><font class="lisp">(nreconc <!-- open: 209, close: 207 --><font class="italic">x y</font><!-- open: 209, close: 208 -->)</font><!-- open: 209, close: 209 --> <!-- MATCHED MATCHED MATCHED --> is exactly the same as 
<!-- open: 210, close: 209 --><font class="lisp">(nconc (nreverse <!-- open: 211, close: 209 --><font class="italic">x</font><!-- open: 211, close: 210 -->) <!-- open: 212, close: 210 --><font class="italic">y</font><!-- open: 212, close: 211 -->)</font><!-- open: 212, close: 212 --> <!-- MATCHED MATCHED MATCHED --> except that it is more 
efficient.  Both <!-- open: 213, close: 212 --><font class="italic">x</font><!-- open: 213, close: 213 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 214, close: 213 --><font class="italic">y</font><!-- open: 214, close: 214 --> <!-- MATCHED MATCHED MATCHED --> should be lists.

<!-- open: 215, close: 214 --><font class="lisp">nreconc</font><!-- open: 215, close: 215 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun nreconc (x y)
    (cond ((null x) y)
          ((nreverse1 x y)) ))
</pre>
using the same <!-- open: 216, close: 215 --><font class="lisp">nreverse1</font><!-- open: 216, close: 216 --> <!-- MATCHED MATCHED MATCHED --> as above.
</div>


<div class='defmac' id='push'><font class='exdent'><font class='funcname' id='push'>push</font><font class="italic"> Macro</font></br></font><!-- end font_exdent -->The form is <!-- open: 217, close: 216 --><font class="lisp">(push <!-- open: 218, close: 216 --><font class="italic">item place</font><!-- open: 218, close: 217 -->)</font><!-- open: 218, close: 218 --> <!-- MATCHED MATCHED MATCHED -->, where <!-- open: 219, close: 218 --><font class="italic">item</font><!-- open: 219, close: 219 --> <!-- MATCHED MATCHED MATCHED --> is an
arbitrary object and <!-- open: 220, close: 219 --><font class="italic">place</font><!-- open: 220, close: 220 --> <!-- MATCHED MATCHED MATCHED --> is a reference to a cell containing
a list.  Usually <!-- open: 221, close: 220 --><font class="italic">place</font><!-- open: 221, close: 221 --> <!-- MATCHED MATCHED MATCHED --> is the name of a variable.  <!-- open: 222, close: 221 --><font class="italic">item</font><!-- open: 222, close: 222 --> <!-- MATCHED MATCHED MATCHED -->
is consed onto the front of the list.

The form
<pre class='lisp'>
(push (hairy-function x y z) variable)
</pre>
replaces the commonly-used construct
<pre class='lisp'>
(setq variable (cons (hairy-function x y z) variable))
</pre>
and is intended to be more explicit and esthetic.
In general, <!-- open: 223, close: 222 --><font class="lisp">(push <!-- open: 224, close: 222 --><font class="italic">item place</font><!-- open: 224, close: 223 -->)</font><!-- open: 224, close: 224 --> <!-- MATCHED MATCHED MATCHED --> expands into
<!-- open: 225, close: 224 --><font class="lisp">(setf <!-- open: 226, close: 224 --><font class="italic">place</font><!-- open: 226, close: 225 --> (cons <!-- open: 227, close: 225 --><font class="italic">item place</font><!-- open: 227, close: 226 -->))</font><!-- open: 227, close: 227 --> <!-- MATCHED MATCHED MATCHED -->.
(See <font color='red'>LINK:(</font>setf-fun) for an explanation of <!-- open: 228, close: 227 --><font class="lisp">setf</font><!-- open: 228, close: 228 --> <!-- MATCHED MATCHED MATCHED -->.)
</div>

<div class='defmac' id='pop'><font class='exdent'><font class='funcname' id='pop'>pop</font><font class="italic"> Macro</font></br></font><!-- end font_exdent -->The form is <!-- open: 229, close: 228 --><font class="lisp">(pop <!-- open: 230, close: 228 --><font class="italic">place</font><!-- open: 230, close: 229 -->)</font><!-- open: 230, close: 230 --> <!-- MATCHED MATCHED MATCHED -->.  The result is
the <!-- open: 231, close: 230 --><font class="lisp">car</font><!-- open: 231, close: 231 --> <!-- MATCHED MATCHED MATCHED --> of the contents of <!-- open: 232, close: 231 --><font class="italic">place</font><!-- open: 232, close: 232 --> <!-- MATCHED MATCHED MATCHED -->, and as a side-effect
the <!-- open: 233, close: 232 --><font class="lisp">cdr</font><!-- open: 233, close: 233 --> <!-- MATCHED MATCHED MATCHED --> of the contents is stored back into <!-- open: 234, close: 233 --><font class="italic">place</font><!-- open: 234, close: 234 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq x '(a b c))
(pop x) =&gt; a
x =&gt; (b c)
</pre>
In general, <!-- open: 235, close: 234 --><font class="lisp">(pop <!-- open: 236, close: 234 --><font class="italic">place</font><!-- open: 236, close: 235 -->)</font><!-- open: 236, close: 236 --> <!-- MATCHED MATCHED MATCHED --> expands into 
<!-- open: 237, close: 236 --><font class="lisp">(prog1 (car <!-- open: 238, close: 236 --><font class="italic">place</font><!-- open: 238, close: 237 -->) (setf <!-- open: 239, close: 237 --><font class="italic">place</font><!-- open: 239, close: 238 --> (cdr <!-- open: 240, close: 238 --><font class="italic">place</font><!-- open: 240, close: 239 -->)))</font><!-- open: 240, close: 240 --> <!-- MATCHED MATCHED MATCHED -->.
(See <font color='red'>LINK:(</font>setf-fun) for an explanation of <!-- open: 241, close: 240 --><font class="lisp">setf</font><!-- open: 241, close: 241 --> <!-- MATCHED MATCHED MATCHED -->.)
</div>

<div class='defun' id='butlast'>
  <font class='exdent'>
    <font class='funcname'>butlast </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
This creates and returns a list with the same elements as <!-- open: 242, close: 241 --><font class="italic">list</font><!-- open: 242, close: 242 --> <!-- MATCHED MATCHED MATCHED -->,
excepting the last element.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(butlast '(a b c d)) =&gt; (a b c)
(butlast '((a b) (c d)) =&gt; ((a b))
(butlast '(a)) =&gt; nil
(butlast nil) =&gt; nil
</pre>
The name is from the phrase "all elements but the last".
</div>

<div class='defun' id='nbutlast'>
  <font class='exdent'>
    <font class='funcname'>nbutlast </font>
    <font class='italic' color='purple'>list</font>
  </font><br>
This is the destructive version of <!-- open: 243, close: 242 --><font class="lisp">butlast</font><!-- open: 243, close: 243 --> <!-- MATCHED MATCHED MATCHED -->; it changes the cdr of
the second-to-last cons of the list to nil.  If there is no
second-to-last cons (that is, if the list has fewer than two elements)
it returns <!-- open: 244, close: 243 --><font class="lisp">nil</font><!-- open: 244, close: 244 --> <!-- MATCHED MATCHED MATCHED -->. 
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(setq foo '(a b c d))
(nbutlast foo) =&gt; (a b c)
foo =&gt; (a b c)
(nbutlast '(a)) =&gt; nil
</pre>
</div>

<div class='defun' id='firstn'>
  <font class='exdent'>
    <font class='funcname'>firstn </font>
    <font class='italic' color='purple'>n list</font>
  </font><br>
<!-- open: 245, close: 244 --><font class="lisp">firstn</font><!-- open: 245, close: 245 --> <!-- MATCHED MATCHED MATCHED --> returns a list of length <!-- open: 246, close: 245 --><font class="italic">n</font><!-- open: 246, close: 246 --> <!-- MATCHED MATCHED MATCHED -->, whose elements are the
first <!-- open: 247, close: 246 --><font class="italic">n</font><!-- open: 247, close: 247 --> <!-- MATCHED MATCHED MATCHED --> elements of <!-- open: 248, close: 247 --><font class="lisp">list</font><!-- open: 248, close: 248 --> <!-- MATCHED MATCHED MATCHED -->.  If <!-- open: 249, close: 248 --><font class="italic">list</font><!-- open: 249, close: 249 --> <!-- MATCHED MATCHED MATCHED --> is fewer than
<!-- open: 250, close: 249 --><font class="italic">n</font><!-- open: 250, close: 250 --> <!-- MATCHED MATCHED MATCHED --> elements long, the remaining elements of the returned list
will be <!-- open: 251, close: 250 --><font class="lisp">nil</font><!-- open: 251, close: 251 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(firstn 2 '(a b c d)) =&gt; (a b)
(firstn 0 '(a b c d)) =&gt; nil
(firstn 6 '(a b c d)) =&gt; (a b c d nil nil)
</pre>
</div>

<div class='defun' id='ldiff'>
  <font class='exdent'>
    <font class='funcname'>ldiff </font>
    <font class='italic' color='purple'>list sublist</font>
  </font><br>
<!-- open: 252, close: 251 --><font class="italic">list</font><!-- open: 252, close: 252 --> <!-- MATCHED MATCHED MATCHED --> should be a list, and <!-- open: 253, close: 252 --><font class="italic">sublist</font><!-- open: 253, close: 253 --> <!-- MATCHED MATCHED MATCHED --> should be a sublist
of <!-- open: 254, close: 253 --><font class="italic">list</font><!-- open: 254, close: 254 --> <!-- MATCHED MATCHED MATCHED -->, i.e. one of the conses that make up <!-- open: 255, close: 254 --><font class="italic">list</font><!-- open: 255, close: 255 --> <!-- MATCHED MATCHED MATCHED -->.
<!-- open: 256, close: 255 --><font class="lisp">ldiff</font><!-- open: 256, close: 256 --> <!-- MATCHED MATCHED MATCHED --> (meaning List Difference) will return a new list,
whose elements are those elements of <!-- open: 257, close: 256 --><font class="italic">list</font><!-- open: 257, close: 257 --> <!-- MATCHED MATCHED MATCHED --> that appear before
<!-- open: 258, close: 257 --><font class="italic">sublist</font><!-- open: 258, close: 258 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(setq x '(a b c d e))
(setq y (cdddr x)) =&gt; (d e)
(ldiff x y) =&gt; (a b c)
<!-- open: 259, close: 258 --><font class="main">but</font><!-- open: 259, close: 259 --> <!-- MATCHED MATCHED MATCHED -->
(ldiff '(a b c d) '(c d)) =&gt; (a b c d)
<!-- open: 260, close: 259 --><font class="main">since the sublist was not <!-- open: 261, close: 259 --><font class="lisp">eq</font><!-- open: 261, close: 260 --> to any part of the list.</font><!-- open: 261, close: 261 --> <!-- MATCHED MATCHED MATCHED -->
</pre>
</div>

<div class='section' id='7.3'>7.3 Alteration of List Structure</div>
The functions <!-- open: 262, close: 261 --><font class="lisp">rplaca</font><!-- open: 262, close: 262 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 263, close: 262 --><font class="lisp">rplacd</font><!-- open: 263, close: 263 --> <!-- MATCHED MATCHED MATCHED -->
are used to make alterations in already-existing
list structure; that is, to change the cars and cdrs of existing conses.
  The structure is not copied but is physically altered;
hence caution should be exercised when using these functions, as
strange side-effects can occur if portions of list structure become
shared unbeknownst to the programmer.
The <!-- open: 264, close: 263 --><font class="lisp">nconc</font><!-- open: 264, close: 264 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 265, close: 264 --><font class="lisp">nreverse</font><!-- open: 265, close: 265 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 266, close: 265 --><font class="lisp">nreconc</font><!-- open: 266, close: 266 --> <!-- MATCHED MATCHED MATCHED -->, and <!-- open: 267, close: 266 --><font class="lisp">nbutlast</font><!-- open: 267, close: 267 --> <!-- MATCHED MATCHED MATCHED --> functions already
described, and the <!-- open: 268, close: 267 --><font class="lisp">delq</font><!-- open: 268, close: 268 --> <!-- MATCHED MATCHED MATCHED --> family described later,
have the same property.  However, they are normally not
used for this side-effect; rather, the list-structure modification
is purely for efficiency and compatible non-modifying functions
are provided.

<div class='defun' id='rplaca'>
  <font class='exdent'>
    <font class='funcname'>rplaca </font>
    <font class='italic' color='purple'>x y</font>
  </font><br>
<!-- open: 269, close: 268 --><font class="lisp">(rplaca <!-- open: 270, close: 268 --><font class="italic">x y</font><!-- open: 270, close: 269 -->)</font><!-- open: 270, close: 270 --> <!-- MATCHED MATCHED MATCHED --> changes the car of <!-- open: 271, close: 270 --><font class="italic">x</font><!-- open: 271, close: 271 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 272, close: 271 --><font class="italic">y</font><!-- open: 272, close: 272 --> <!-- MATCHED MATCHED MATCHED --> and returns
(the modified) <!-- open: 273, close: 272 --><font class="italic">x</font><!-- open: 273, close: 273 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 274, close: 273 --><font class="italic">x</font><!-- open: 274, close: 274 --> <!-- MATCHED MATCHED MATCHED --> should be a cons, but <!-- open: 275, close: 274 --><font class="italic">y</font><!-- open: 275, close: 275 --> <!-- MATCHED MATCHED MATCHED --> may be any Lisp object.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq g '(a b c))
(rplaca (cdr g) 'd) =&gt; (d c)
<!-- open: 276, close: 275 --><font class="main">Now</font><!-- open: 276, close: 276 --> <!-- MATCHED MATCHED MATCHED --> g =&gt; (a d c)
</pre>
</div>

<div class='defun' id='rplacd'>
  <font class='exdent'>
    <font class='funcname'>rplacd </font>
    <font class='italic' color='purple'>x y</font>
  </font><br>
<!-- open: 277, close: 276 --><font class="lisp">(rplacd <!-- open: 278, close: 276 --><font class="italic">x y</font><!-- open: 278, close: 277 -->)</font><!-- open: 278, close: 278 --> <!-- MATCHED MATCHED MATCHED --> changes the cdr of <!-- open: 279, close: 278 --><font class="italic">x</font><!-- open: 279, close: 279 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 280, close: 279 --><font class="italic">y</font><!-- open: 280, close: 280 --> <!-- MATCHED MATCHED MATCHED --> and returns
(the modified) <!-- open: 281, close: 280 --><font class="italic">x</font><!-- open: 281, close: 281 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 282, close: 281 --><font class="italic">x</font><!-- open: 282, close: 282 --> <!-- MATCHED MATCHED MATCHED --> should be a cons, but <!-- open: 283, close: 282 --><font class="italic">y</font><!-- open: 283, close: 283 --> <!-- MATCHED MATCHED MATCHED --> may be any Lisp object.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq x '(a b c))
(rplacd x 'd) =&gt; (a . d)
<!-- open: 284, close: 283 --><font class="main">Now</font><!-- open: 284, close: 284 --> <!-- MATCHED MATCHED MATCHED --> x =&gt; (a . d)
</pre>
Note to Maclisp users: <!-- open: 285, close: 284 --><font class="lisp">rplacd</font><!-- open: 285, close: 285 --> <!-- MATCHED MATCHED MATCHED --> should not be used to set the property
list of a symbol, although there is a compatibility mode in which it will work.
See <!-- open: 286, close: 285 --><font class="lisp">car</font><!-- open: 286, close: 286 --> <!-- MATCHED MATCHED MATCHED --> (<font color='red'>LINK:(</font>car-fun)).  The right way to set a property list is with
<!-- open: 287, close: 286 --><font class="lisp">setplist</font><!-- open: 287, close: 287 --> <!-- MATCHED MATCHED MATCHED --> (see <font color='red'>LINK:(</font>setplist-fun)).
'findex "setplist"
</div>

<p class='cindent'><!-- "substitution" -->
<div class='defun' id='subst'>
  <font class='exdent'>
    <font class='funcname'>subst </font>
    <font class='italic' color='purple'>new old s-exp</font>
  </font><br>
<!-- open: 288, close: 287 --><font class="lisp">(subst <!-- open: 289, close: 287 --><font class="italic">new old s-exp</font><!-- open: 289, close: 288 -->)</font><!-- open: 289, close: 289 --> <!-- MATCHED MATCHED MATCHED --> substitutes <!-- open: 290, close: 289 --><font class="italic">new</font><!-- open: 290, close: 290 --> <!-- MATCHED MATCHED MATCHED --> for all occurrences of <!-- open: 291, close: 290 --><font class="italic">old</font><!-- open: 291, close: 291 --> <!-- MATCHED MATCHED MATCHED -->
in <!-- open: 292, close: 291 --><font class="italic">s-exp</font><!-- open: 292, close: 292 --> <!-- MATCHED MATCHED MATCHED -->, and returns the modified copy of <!-- open: 293, close: 292 --><font class="italic">s-exp</font><!-- open: 293, close: 293 --> <!-- MATCHED MATCHED MATCHED -->.  The original <!-- open: 294, close: 293 --><font class="italic">s-exp</font><!-- open: 294, close: 294 --> <!-- MATCHED MATCHED MATCHED -->
is unchanged, as <!-- open: 295, close: 294 --><font class="lisp">subst</font><!-- open: 295, close: 295 --> <!-- MATCHED MATCHED MATCHED --> recursively copies all of <!-- open: 296, close: 295 --><font class="italic">s-exp</font><!-- open: 296, close: 296 --> <!-- MATCHED MATCHED MATCHED --> replacing
elements <!-- open: 297, close: 296 --><font class="lisp">equal</font><!-- open: 297, close: 297 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 298, close: 297 --><font class="italic">old</font><!-- open: 298, close: 298 --> <!-- MATCHED MATCHED MATCHED --> as it goes.  If <!-- open: 299, close: 298 --><font class="italic">new</font><!-- open: 299, close: 299 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 300, close: 299 --><font class="italic">old</font><!-- open: 300, close: 300 --> <!-- MATCHED MATCHED MATCHED --> are <!-- open: 301, close: 300 --><font class="lisp">nil</font><!-- open: 301, close: 301 --> <!-- MATCHED MATCHED MATCHED -->,
<!-- open: 302, close: 301 --><font class="italic">s-exp</font><!-- open: 302, close: 302 --> <!-- MATCHED MATCHED MATCHED --> is just copied, which is a convenient way to copy arbitrary list
structure. 
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(subst 'Tempest 'Hurricane
       '(Shakespeare wrote (The Hurricane)))
    =&gt; (Shakespeare wrote (The Tempest))
</pre>

<!-- open: 303, close: 302 --><font class="lisp">subst</font><!-- open: 303, close: 303 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:

<pre class='lisp'>
(defun subst (new old s-exp)
    (cond ((equal s-exp old) new) ;<!-- open: 304, close: 303 --><font class="main">if item eq to old, replace.</font><!-- open: 304, close: 304 --> <!-- MATCHED MATCHED MATCHED -->
          ((atom s-exp) s-exp)    ;<!-- open: 305, close: 304 --><font class="main">if no substructure, return arg.</font><!-- open: 305, close: 305 --> <!-- MATCHED MATCHED MATCHED -->
          ((cons (subst new old (car s-exp))  ;<!-- open: 306, close: 305 --><font class="main">otherwise recurse.</font><!-- open: 306, close: 306 --> <!-- MATCHED MATCHED MATCHED -->
                 (subst new old (cdr s-exp))))))
</pre>
Note that this function is not "destructive"; that is, it does not change
the <!-- open: 307, close: 306 --><font class="italic">car</font><!-- open: 307, close: 307 --> <!-- MATCHED MATCHED MATCHED --> or <!-- open: 308, close: 307 --><font class="italic">cdr</font><!-- open: 308, close: 308 --> <!-- MATCHED MATCHED MATCHED --> of any already-existing list structure.
</div>

<div class='defun' id='nsubst'>
  <font class='exdent'>
    <font class='funcname'>nsubst </font>
    <font class='italic' color='purple'>new old s-exp</font>
  </font><br>
<!-- open: 309, close: 308 --><font class="lisp">nsubst</font><!-- open: 309, close: 309 --> <!-- MATCHED MATCHED MATCHED --> is a destructive version of <!-- open: 310, close: 309 --><font class="lisp">subst</font><!-- open: 310, close: 310 --> <!-- MATCHED MATCHED MATCHED -->.  The list structure of
<!-- open: 311, close: 310 --><font class="italic">s-exp</font><!-- open: 311, close: 311 --> <!-- MATCHED MATCHED MATCHED --> is altered by replacing each occurrence of <!-- open: 312, close: 311 --><font class="italic">old</font><!-- open: 312, close: 312 --> <!-- MATCHED MATCHED MATCHED --> with
<!-- open: 313, close: 312 --><font class="italic">new</font><!-- open: 313, close: 313 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 314, close: 313 --><font class="lisp">nsubst</font><!-- open: 314, close: 314 --> <!-- MATCHED MATCHED MATCHED --> could have been defined as
<pre class='lisp'>
(defun nsubst (new old s-exp)
    (cond ((eq s-exp old) new)	  ;<!-- open: 315, close: 314 --><font class="main">If item eq to old, replace.</font><!-- open: 315, close: 315 --> <!-- MATCHED MATCHED MATCHED -->
          ((atom s-exp) s-exp)    ;<!-- open: 316, close: 315 --><font class="main">If no substructure, return arg.</font><!-- open: 316, close: 316 --> <!-- MATCHED MATCHED MATCHED -->
	  (t ;; <!-- open: 317, close: 316 --><font class="main">Otherwise, recurse.</font><!-- open: 317, close: 317 --> <!-- MATCHED MATCHED MATCHED -->
	     (rplaca s-exp (nsubst new old (car s-exp)))
	     (rplacd s-exp (nsubst new old (cdr s-exp)))
	     s-exp)))
</pre>
</div>

<div class='defun' id='sublis'>
  <font class='exdent'>
    <font class='funcname'>sublis </font>
    <font class='italic' color='purple'>alist S-expression</font>
  </font><br>
<!-- open: 318, close: 317 --><font class="lisp">sublis</font><!-- open: 318, close: 318 --> <!-- MATCHED MATCHED MATCHED --> makes substitutions for symbols in an S-expression
(a structure of nested lists).
The first argument to <!-- open: 319, close: 318 --><font class="lisp">sublis</font><!-- open: 319, close: 319 --> <!-- MATCHED MATCHED MATCHED --> is an association list (see the next
section).  The second argument is the S-expression in which
substitutions are to be made.  <!-- open: 320, close: 319 --><font class="lisp">sublis</font><!-- open: 320, close: 320 --> <!-- MATCHED MATCHED MATCHED --> looks at all symbols
in the S-expression; if a symbol appears in the association
list occurrences of it are replaced by the object it is associated
with.  The argument is not modified; new conses are created where
necessary and only where necessary, so the newly created structure
shares as much of its substructure as possible with the old.  For
example, if no substitutions are made, the result is <!-- open: 321, close: 320 --><font class="lisp">eq</font><!-- open: 321, close: 321 --> <!-- MATCHED MATCHED MATCHED --> to the old
S-expression. 
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(sublis '((x . 100) (z . zprime))
        '(plus x (minus g z x p) 4))
   =&gt; (plus 100 (minus g zprime 100 p) 4)
</pre>
</div>

<div class='defun' id='nsublis'>
  <font class='exdent'>
    <font class='funcname'>nsublis </font>
    <font class='italic' color='purple'>alist S-expression</font>
  </font><br>
<!-- open: 322, close: 321 --><font class="lisp">nsublis</font><!-- open: 322, close: 322 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 323, close: 322 --><font class="lisp">sublis</font><!-- open: 323, close: 323 --> <!-- MATCHED MATCHED MATCHED --> but changes the original list structure
instead of creating new.
</div>

<div class='section' id='7.4'>7.4 Cdr-Coding</div>
	There is an issue which those who must be concerned with
efficiency will need to think about.  In the Lisp Machine there are
actually two kinds of lists; normal lists and <!-- open: 324, close: 323 --><font class="italic">cdr-coded</font><!-- open: 324, close: 324 --> <!-- MATCHED MATCHED MATCHED --> lists.  Normal
lists take two words for each <!-- open: 325, close: 324 --><font class="italic">cons</font><!-- open: 325, close: 325 --> <!-- MATCHED MATCHED MATCHED -->, while cdr-coded lists require
only one word for each <!-- open: 326, close: 325 --><font class="italic">cons</font><!-- open: 326, close: 326 --> <!-- MATCHED MATCHED MATCHED -->.  The saving is achieved by taking
advantage of the usual structure of lists to avoid storing the redundant cdrs
which link together the conses which make up the list.  Ordinarily,
<!-- open: 327, close: 326 --><font class="lisp">rplacd</font><!-- open: 327, close: 327 --> <!-- MATCHED MATCHED MATCHED -->'ing such a list would be impossible, since there is no explicit
representation of the cdr to be modified.  However, in the Lisp machine system
it is merely somewhat expensive; a 2-word ordinary
cons must be allocated and linked into the list by an invisible pointer.
This is slower than an ordinary <!-- open: 328, close: 327 --><font class="lisp">rplacd</font><!-- open: 328, close: 328 --> <!-- MATCHED MATCHED MATCHED -->,
uses extra space, and slows down future accessing of the list.

	One should try to use normal lists for those data structures that will
be subject to <!-- open: 329, close: 328 --><font class="lisp">rplacd</font><!-- open: 329, close: 329 --> <!-- MATCHED MATCHED MATCHED -->ing operations, including <!-- open: 330, close: 329 --><font class="lisp">nconc</font><!-- open: 330, close: 330 --> <!-- MATCHED MATCHED MATCHED --> and
<!-- open: 331, close: 330 --><font class="lisp">nreverse</font><!-- open: 331, close: 331 --> <!-- MATCHED MATCHED MATCHED -->, and cdr-coded lists for other structures.
The functions <!-- open: 332, close: 331 --><font class="lisp">cons</font><!-- open: 332, close: 332 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 333, close: 332 --><font class="lisp">xcons</font><!-- open: 333, close: 333 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 334, close: 333 --><font class="lisp">ncons</font><!-- open: 334, close: 334 --> <!-- MATCHED MATCHED MATCHED -->, and their area variants make normal lists.
The functions <!-- open: 335, close: 334 --><font class="lisp">list</font><!-- open: 335, close: 335 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 336, close: 335 --><font class="lisp">list*</font><!-- open: 336, close: 336 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 337, close: 336 --><font class="lisp">list-in-area</font><!-- open: 337, close: 337 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 338, close: 337 --><font class="lisp">make-list</font><!-- open: 338, close: 338 --> <!-- MATCHED MATCHED MATCHED -->,
and <!-- open: 339, close: 338 --><font class="lisp">append</font><!-- open: 339, close: 339 --> <!-- MATCHED MATCHED MATCHED --> make cdr-coded lists.  The other list-creating functions,
including <!-- open: 340, close: 339 --><font class="lisp">read</font><!-- open: 340, close: 340 --> <!-- MATCHED MATCHED MATCHED -->,
currently make normal lists, but this should not be relied upon.
Some functions, such as <!-- open: 341, close: 340 --><font class="lisp">sort</font><!-- open: 341, close: 341 --> <!-- MATCHED MATCHED MATCHED -->, take special care to operate
efficiently on cdr-coded lists (<!-- open: 342, close: 341 --><font class="lisp">sort</font><!-- open: 342, close: 342 --> <!-- MATCHED MATCHED MATCHED --> treats them as arrays).
<!-- open: 343, close: 342 --><font class="lisp">nreverse</font><!-- open: 343, close: 343 --> <!-- MATCHED MATCHED MATCHED --> is rather slow on cdr-coded lists, currently, since it
simple-mindedly uses <!-- open: 344, close: 343 --><font class="lisp">rplacd</font><!-- open: 344, close: 344 --> <!-- MATCHED MATCHED MATCHED -->, however this will be changed.

	It is currently <!-- open: 345, close: 344 --><font class="italic">not</font><!-- open: 345, close: 345 --> <!-- MATCHED MATCHED MATCHED --> planned that the garbage collector
compact ordinary lists into cdr-coded lists.  <!-- open: 346, close: 345 --><font class="lisp">(append <!-- open: 347, close: 345 --><font class="italic">x</font><!-- open: 347, close: 346 --> nil)</font><!-- open: 347, close: 347 --> <!-- MATCHED MATCHED MATCHED -->
is a suitable way to copy a list, converting it into cdr-coded form.

<div class='section' id='7.5'>7.5 Tables</div>
Lisp Machine Lisp includes several functions which simplify the maintenance
of tabular data structures of several varieties.  The simplest is
a plain list of items, which models (approximately) the concept of a <!-- open: 348, close: 347 --><font class="italic">set</font><!-- open: 348, close: 348 --> <!-- MATCHED MATCHED MATCHED -->.
<p class='cindent' id='cdr-code'><!-- "set" -->
There are functions to add (<!-- open: 349, close: 348 --><font class="lisp">cons</font><!-- open: 349, close: 349 --> <!-- MATCHED MATCHED MATCHED -->), remove (<!-- open: 350, close: 349 --><font class="lisp">delete</font><!-- open: 350, close: 350 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 351, close: 350 --><font class="lisp">delq</font><!-- open: 351, close: 351 --> <!-- MATCHED MATCHED MATCHED -->,
<!-- open: 352, close: 351 --><font class="lisp">del</font><!-- open: 352, close: 352 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 353, close: 352 --><font class="lisp">del-if</font><!-- open: 353, close: 353 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 354, close: 353 --><font class="lisp">del-if-not</font><!-- open: 354, close: 354 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 355, close: 354 --><font class="lisp">remove</font><!-- open: 355, close: 355 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 356, close: 355 --><font class="lisp">remq</font><!-- open: 356, close: 356 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 357, close: 356 --><font class="lisp">rem</font><!-- open: 357, close: 357 --> <!-- MATCHED MATCHED MATCHED -->,
<!-- open: 358, close: 357 --><font class="lisp">rem-if</font><!-- open: 358, close: 358 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 359, close: 358 --><font class="lisp">rem-if-not</font><!-- open: 359, close: 359 --> <!-- MATCHED MATCHED MATCHED -->),
and search for (<!-- open: 360, close: 359 --><font class="lisp">member</font><!-- open: 360, close: 360 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 361, close: 360 --><font class="lisp">memq</font><!-- open: 361, close: 361 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 362, close: 361 --><font class="lisp">mem</font><!-- open: 362, close: 362 --> <!-- MATCHED MATCHED MATCHED -->) items in a list.
Set union, intersection, and difference functions are easily written using these.


<p class='cindent'><!-- "association lists" -->
<!-- open: 363, close: 362 --><font class="italic">Association lists</font><!-- open: 363, close: 363 --> <!-- MATCHED MATCHED MATCHED --> are very commonly used.  An association list
is a list of conses.  The car of each cons is a "key" and the cdr
is a "datum", or a list of associated data.  The functions
<!-- open: 364, close: 363 --><font class="lisp">assoc</font><!-- open: 364, close: 364 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 365, close: 364 --><font class="lisp">assq</font><!-- open: 365, close: 365 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 366, close: 365 --><font class="lisp">ass</font><!-- open: 366, close: 366 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 367, close: 366 --><font class="lisp">memass</font><!-- open: 367, close: 367 --> <!-- MATCHED MATCHED MATCHED -->, and <!-- open: 368, close: 367 --><font class="lisp">rassoc</font><!-- open: 368, close: 368 --> <!-- MATCHED MATCHED MATCHED -->
may be used to retrieve the data, given the key.

<!-- open: 369, close: 368 --><font class="italic">Structured records</font><!-- open: 369, close: 369 --> <!-- MATCHED MATCHED MATCHED --> can be stored as association lists or as
stereotyped cons-structures where each element of the structure has a certain
car-cdr path associated with it.  However, these are better implemented
using structure macros (see <a href='dfstr.html#defstruct'>this link</a>).

Simple list-structure is very convenient, but may not be efficient enough
for large data bases because it takes a long time to search a long list.
Lisp Machine lisp includes a hashing function (<!-- open: 370, close: 369 --><font class="lisp">sxhash</font><!-- open: 370, close: 370 --> <!-- MATCHED MATCHED MATCHED -->) which
aids in the construction of more efficient, hairier structures.


<div class='defun' id='memq'>
  <font class='exdent'>
    <font class='funcname'>memq </font>
    <font class='italic' color='purple'>item list</font>
  </font><br>
<!-- open: 371, close: 370 --><font class="lisp">(memq <!-- open: 372, close: 370 --><font class="italic">item list</font><!-- open: 372, close: 371 -->)</font><!-- open: 372, close: 372 --> <!-- MATCHED MATCHED MATCHED --> returns <!-- open: 373, close: 372 --><font class="lisp">nil</font><!-- open: 373, close: 373 --> <!-- MATCHED MATCHED MATCHED --> if <!-- open: 374, close: 373 --><font class="italic">item</font><!-- open: 374, close: 374 --> <!-- MATCHED MATCHED MATCHED --> is not one of the elements of
<!-- open: 375, close: 374 --><font class="italic">list</font><!-- open: 375, close: 375 --> <!-- MATCHED MATCHED MATCHED -->.  Otherwise, it returns the portion of <!-- open: 376, close: 375 --><font class="italic">list</font><!-- open: 376, close: 376 --> <!-- MATCHED MATCHED MATCHED --> beginning
with the first occurrence of <!-- open: 377, close: 376 --><font class="italic">item</font><!-- open: 377, close: 377 --> <!-- MATCHED MATCHED MATCHED -->.  The comparison is made by
<!-- open: 378, close: 377 --><font class="lisp">eq</font><!-- open: 378, close: 378 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 379, close: 378 --><font class="italic">list</font><!-- open: 379, close: 379 --> <!-- MATCHED MATCHED MATCHED --> is searched on the top level only. 
Because <!-- open: 380, close: 379 --><font class="lisp">memq</font><!-- open: 380, close: 380 --> <!-- MATCHED MATCHED MATCHED --> returns <!-- open: 381, close: 380 --><font class="lisp">nil</font><!-- open: 381, close: 381 --> <!-- MATCHED MATCHED MATCHED --> if it doesn't find anything,
and something non-<!-- open: 382, close: 381 --><font class="lisp">nil</font><!-- open: 382, close: 382 --> <!-- MATCHED MATCHED MATCHED --> if it finds something, it is often used as a predicate.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(memq 'a '(1 2 3 4)) =&gt; nil
(memq 'a '(g (x y) c a d e a f)) =&gt; (a d e a f)
</pre>
Note that the value returned by <!-- open: 383, close: 382 --><font class="lisp">memq</font><!-- open: 383, close: 383 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 384, close: 383 --><font class="lisp">eq</font><!-- open: 384, close: 384 --> <!-- MATCHED MATCHED MATCHED --> to the portion of the list
beginning with <!-- open: 385, close: 384 --><font class="italic">a</font><!-- open: 385, close: 385 --> <!-- MATCHED MATCHED MATCHED -->.
Thus <!-- open: 386, close: 385 --><font class="lisp">rplaca</font><!-- open: 386, close: 386 --> <!-- MATCHED MATCHED MATCHED --> on the result of <!-- open: 387, close: 386 --><font class="lisp">memq</font><!-- open: 387, close: 387 --> <!-- MATCHED MATCHED MATCHED --> may be used,
if you first check to make sure <!-- open: 388, close: 387 --><font class="lisp">memq</font><!-- open: 388, close: 388 --> <!-- MATCHED MATCHED MATCHED --> did not return <!-- open: 389, close: 388 --><font class="lisp">nil</font><!-- open: 389, close: 389 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(*catch 'lose
	(rplaca (or (memq x z)
		    (*throw 'lose nil))
		y)
	)	
</pre>

<!-- open: 390, close: 389 --><font class="lisp">memq</font><!-- open: 390, close: 390 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun memq (item list)
    (cond ((atom list) nil)
          ((eq item (car list)) list)
          ((memq item (cdr list))) ))
</pre>

<!-- open: 391, close: 390 --><font class="lisp">memq</font><!-- open: 391, close: 391 --> <!-- MATCHED MATCHED MATCHED --> is hand-coded in microcode and therefore especially fast.
</div>

<div class='defun' id='member'>
  <font class='exdent'>
    <font class='funcname'>member </font>
    <font class='italic' color='purple'>item list</font>
  </font><br>
<!-- open: 392, close: 391 --><font class="lisp">member</font><!-- open: 392, close: 392 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 393, close: 392 --><font class="lisp">memq</font><!-- open: 393, close: 393 --> <!-- MATCHED MATCHED MATCHED -->, except <!-- open: 394, close: 393 --><font class="lisp">equal</font><!-- open: 394, close: 394 --> <!-- MATCHED MATCHED MATCHED --> is used for the comparison,
instead of <!-- open: 395, close: 394 --><font class="lisp">eq</font><!-- open: 395, close: 395 --> <!-- MATCHED MATCHED MATCHED -->.

<!-- open: 396, close: 395 --><font class="lisp">member</font><!-- open: 396, close: 396 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun member (item list)
    (cond ((null list) nil)
          ((equal item (car list)) list)
          ((member item (cdr list))) ))
</pre>
</div>


<div class='defun' id='mem'>
  <font class='exdent'>
    <font class='funcname'>mem </font>
    <font class='italic' color='purple'>predicate item list</font>
  </font><br>
<!-- open: 397, close: 396 --><font class="lisp">mem</font><!-- open: 397, close: 397 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 398, close: 397 --><font class="lisp">memq</font><!-- open: 398, close: 398 --> <!-- MATCHED MATCHED MATCHED --> except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of <!-- open: 399, close: 398 --><font class="lisp">eq</font><!-- open: 399, close: 399 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 400, close: 399 --><font class="lisp">(mem 'eq a b)</font><!-- open: 400, close: 400 --> <!-- MATCHED MATCHED MATCHED --> is the same as
<!-- open: 401, close: 400 --><font class="lisp">(memq a b)</font><!-- open: 401, close: 401 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 402, close: 401 --><font class="lisp">(mem 'equal a b)</font><!-- open: 402, close: 402 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 403, close: 402 --><font class="lisp">(member a b)</font><!-- open: 403, close: 403 --> <!-- MATCHED MATCHED MATCHED -->.
	<!-- open: 404, close: 403 --><font class="lisp">mem</font><!-- open: 404, close: 404 --> <!-- MATCHED MATCHED MATCHED --> is usually used with equality predicates other than
<!-- open: 405, close: 404 --><font class="lisp">eq</font><!-- open: 405, close: 405 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 406, close: 405 --><font class="lisp">equal</font><!-- open: 406, close: 406 --> <!-- MATCHED MATCHED MATCHED -->, such
as <!-- open: 407, close: 406 --><font class="lisp">=</font><!-- open: 407, close: 407 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 408, close: 407 --><font class="lisp">char-equal</font><!-- open: 408, close: 408 --> <!-- MATCHED MATCHED MATCHED --> or <!-- open: 409, close: 408 --><font class="lisp">string-equal</font><!-- open: 409, close: 409 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='tailp'>
  <font class='exdent'>
    <font class='funcname'>tailp </font>
    <font class='italic' color='purple'>tail list</font>
  </font><br>
A <!-- open: 410, close: 409 --><font class="italic">tail</font><!-- open: 410, close: 410 --> <!-- MATCHED MATCHED MATCHED --> of a list is anything that can be obtained by taking <!-- open: 411, close: 410 --><font class="lisp">cdr</font><!-- open: 411, close: 411 --> <!-- MATCHED MATCHED MATCHED --> of it zero
or more times.  <!-- open: 412, close: 411 --><font class="lisp">tailp</font><!-- open: 412, close: 412 --> <!-- MATCHED MATCHED MATCHED --> is used to ask whether <!-- open: 413, close: 412 --><font class="italic">tail</font><!-- open: 413, close: 413 --> <!-- MATCHED MATCHED MATCHED --> is a tail of
<!-- open: 414, close: 413 --><font class="italic">list</font><!-- open: 414, close: 414 --> <!-- MATCHED MATCHED MATCHED -->.  That is, it <!-- open: 415, close: 414 --><font class="lisp">cdr</font><!-- open: 415, close: 415 --> <!-- MATCHED MATCHED MATCHED -->'s down <!-- open: 416, close: 415 --><font class="italic">list</font><!-- open: 416, close: 416 --> <!-- MATCHED MATCHED MATCHED --> checking at each step
whether what it has got is <!-- open: 417, close: 416 --><font class="lisp">eq</font><!-- open: 417, close: 417 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 418, close: 417 --><font class="italic">tail</font><!-- open: 418, close: 418 --> <!-- MATCHED MATCHED MATCHED -->.  If so, the value is <!-- open: 419, close: 418 --><font class="lisp">t</font><!-- open: 419, close: 419 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='delq'>
  <font class='exdent'>
    <font class='funcname'>delq </font>
    <font class='italic' color='purple'>item list &optional n</font>
  </font><br>
<!-- open: 420, close: 419 --><font class="lisp">(delq <!-- open: 421, close: 419 --><font class="italic">item list</font><!-- open: 421, close: 420 -->)</font><!-- open: 421, close: 421 --> <!-- MATCHED MATCHED MATCHED --> returns the <!-- open: 422, close: 421 --><font class="italic">list</font><!-- open: 422, close: 422 --> <!-- MATCHED MATCHED MATCHED --> with all top-level
occurrences of <!-- open: 423, close: 422 --><font class="italic">item</font><!-- open: 423, close: 423 --> <!-- MATCHED MATCHED MATCHED --> removed.  <!-- open: 424, close: 423 --><font class="lisp">eq</font><!-- open: 424, close: 424 --> <!-- MATCHED MATCHED MATCHED --> is used for the comparison. 
The argument <!-- open: 425, close: 424 --><font class="italic">list</font><!-- open: 425, close: 425 --> <!-- MATCHED MATCHED MATCHED --> is actually modified (<!-- open: 426, close: 425 --><font class="lisp">rplacd</font><!-- open: 426, close: 426 --> <!-- MATCHED MATCHED MATCHED -->'ed) when instances
of <!-- open: 427, close: 426 --><font class="italic">item</font><!-- open: 427, close: 427 --> <!-- MATCHED MATCHED MATCHED --> are spliced out.  <!-- open: 428, close: 427 --><font class="lisp">delq</font><!-- open: 428, close: 428 --> <!-- MATCHED MATCHED MATCHED --> should be used for value, not
for effect.  That is, use
<pre class='lisp'>
(setq a (delq 'b a))
</pre>
rather than
<pre class='lisp'>
(delq 'b a)
</pre>
The latter is <!-- open: 429, close: 428 --><font class="italic">not</font><!-- open: 429, close: 429 --> <!-- MATCHED MATCHED MATCHED --> equivalent when the first element
of the value of <!-- open: 430, close: 429 --><font class="lisp">a</font><!-- open: 430, close: 430 --> <!-- MATCHED MATCHED MATCHED --> is <!-- open: 431, close: 430 --><font class="lisp">b</font><!-- open: 431, close: 431 --> <!-- MATCHED MATCHED MATCHED -->.

<!-- open: 432, close: 431 --><font class="lisp">(delq <!-- open: 433, close: 431 --><font class="italic">item list n</font><!-- open: 433, close: 432 -->)</font><!-- open: 433, close: 433 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 434, close: 433 --><font class="lisp">(delq <!-- open: 435, close: 433 --><font class="italic">item list</font><!-- open: 435, close: 434 -->)</font><!-- open: 435, close: 435 --> <!-- MATCHED MATCHED MATCHED --> except only the first
<!-- open: 436, close: 435 --><font class="italic">n</font><!-- open: 436, close: 436 --> <!-- MATCHED MATCHED MATCHED --> instances of <!-- open: 437, close: 436 --><font class="italic">item</font><!-- open: 437, close: 437 --> <!-- MATCHED MATCHED MATCHED --> are deleted.  <!-- open: 438, close: 437 --><font class="italic">n</font><!-- open: 438, close: 438 --> <!-- MATCHED MATCHED MATCHED --> is allowed to be zero. 
If <!-- open: 439, close: 438 --><font class="italic">n</font><!-- open: 439, close: 439 --> <!-- MATCHED MATCHED MATCHED --> is greater than the number of occurrences of <!-- open: 440, close: 439 --><font class="italic">item</font><!-- open: 440, close: 440 --> <!-- MATCHED MATCHED MATCHED --> in the
list, all occurrences of <!-- open: 441, close: 440 --><font class="italic">item</font><!-- open: 441, close: 441 --> <!-- MATCHED MATCHED MATCHED --> in the list will be deleted. 
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(delq 'a '(b a c (a b) d a e)) =&gt; (b c (a b) d e)
</pre>

<!-- open: 442, close: 441 --><font class="lisp">delq</font><!-- open: 442, close: 442 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun delq (item list &amp;optional (n 7777777))  ;<!-- open: 443, close: 442 --><font class="main">7777777 as infinity.</font><!-- open: 443, close: 443 --> <!-- MATCHED MATCHED MATCHED -->
    (cond ((or (atom list) (zerop n)) list)
          ((eq item (car list))
	   (delq item (cdr list) (1- n)))
          ((rplacd list (delq item (cdr list) n)))))
</pre>
</div>

<div class='defun' id='delete'>
  <font class='exdent'>
    <font class='funcname'>delete </font>
    <font class='italic' color='purple'>item list &optional n</font>
  </font><br>
<!-- open: 444, close: 443 --><font class="lisp">delete</font><!-- open: 444, close: 444 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 445, close: 444 --><font class="lisp">delq</font><!-- open: 445, close: 445 --> <!-- MATCHED MATCHED MATCHED --> except that <!-- open: 446, close: 445 --><font class="lisp">equal</font><!-- open: 446, close: 446 --> <!-- MATCHED MATCHED MATCHED --> is used for the comparison
instead of <!-- open: 447, close: 446 --><font class="lisp">eq</font><!-- open: 447, close: 447 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='del'>
  <font class='exdent'>
    <font class='funcname'>del </font>
    <font class='italic' color='purple'>predicate item list &optional n</font>
  </font><br>
<!-- open: 448, close: 447 --><font class="lisp">del</font><!-- open: 448, close: 448 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 449, close: 448 --><font class="lisp">delq</font><!-- open: 449, close: 449 --> <!-- MATCHED MATCHED MATCHED --> except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of <!-- open: 450, close: 449 --><font class="lisp">eq</font><!-- open: 450, close: 450 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 451, close: 450 --><font class="lisp">(del 'eq a b)</font><!-- open: 451, close: 451 --> <!-- MATCHED MATCHED MATCHED --> is the same as
<!-- open: 452, close: 451 --><font class="lisp">(delq a b)</font><!-- open: 452, close: 452 --> <!-- MATCHED MATCHED MATCHED -->. (c.f. <!-- open: 453, close: 452 --><font class="lisp">mem</font><!-- open: 453, close: 453 --> <!-- MATCHED MATCHED MATCHED -->, <font color='red'>LINK:(</font>mem-fun))
</div>

<div class='defun' id='remq'>
  <font class='exdent'>
    <font class='funcname'>remq </font>
    <font class='italic' color='purple'>item list &optional n</font>
  </font><br>
<!-- open: 454, close: 453 --><font class="lisp">remq</font><!-- open: 454, close: 454 --> <!-- MATCHED MATCHED MATCHED --> is similar to <!-- open: 455, close: 454 --><font class="lisp">delq</font><!-- open: 455, close: 455 --> <!-- MATCHED MATCHED MATCHED -->, except that the list is not altered;
rather, a new list is returned.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(setq x '(a b c d e f))
(remq 'b x) =&gt; (a c d e f)
x =&gt; (a b c d e f)
(remq 'b '(a b c b a b) 2) =&gt; (a c a b)
</pre>
</div>

<div class='defun' id='remove'>
  <font class='exdent'>
    <font class='funcname'>remove </font>
    <font class='italic' color='purple'>item list &optional n</font>
  </font><br>
<!-- open: 456, close: 455 --><font class="lisp">remove</font><!-- open: 456, close: 456 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 457, close: 456 --><font class="lisp">remq</font><!-- open: 457, close: 457 --> <!-- MATCHED MATCHED MATCHED --> except that <!-- open: 458, close: 457 --><font class="lisp">equal</font><!-- open: 458, close: 458 --> <!-- MATCHED MATCHED MATCHED --> is used for the
comparison instead of <!-- open: 459, close: 458 --><font class="lisp">eq</font><!-- open: 459, close: 459 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='rem'>
  <font class='exdent'>
    <font class='funcname'>rem </font>
    <font class='italic' color='purple'>predicate item list &optional n</font>
  </font><br>
<!-- open: 460, close: 459 --><font class="lisp">rem</font><!-- open: 460, close: 460 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 461, close: 460 --><font class="lisp">remq</font><!-- open: 461, close: 461 --> <!-- MATCHED MATCHED MATCHED --> except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of <!-- open: 462, close: 461 --><font class="lisp">eq</font><!-- open: 462, close: 462 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 463, close: 462 --><font class="lisp">(rem 'eq a b)</font><!-- open: 463, close: 463 --> <!-- MATCHED MATCHED MATCHED --> is the same as
<!-- open: 464, close: 463 --><font class="lisp">(remq a b)</font><!-- open: 464, close: 464 --> <!-- MATCHED MATCHED MATCHED -->. (c.f. <!-- open: 465, close: 464 --><font class="lisp">mem</font><!-- open: 465, close: 465 --> <!-- MATCHED MATCHED MATCHED --> <font color='red'>LINK:(</font>mem-fun))
</div>

<div class='defun' id='rem-if'>
  <font class='exdent'>
    <font class='funcname'>rem-if </font>
    <font class='italic' color='purple'>predicate list</font>
  </font><br>
<!-- open: 466, close: 465 --><font class="italic">predicate</font><!-- open: 466, close: 466 --> <!-- MATCHED MATCHED MATCHED --> should be a function of one argument.
<!-- open: 467, close: 466 --><font class="lisp">rem-if</font><!-- open: 467, close: 467 --> <!-- MATCHED MATCHED MATCHED --> makes a new list by applying <!-- open: 468, close: 467 --><font class="italic">predicate</font><!-- open: 468, close: 468 --> <!-- MATCHED MATCHED MATCHED --> to
all of the elements of <!-- open: 469, close: 468 --><font class="italic">list</font><!-- open: 469, close: 469 --> <!-- MATCHED MATCHED MATCHED --> and removing the ones for which the predicate 
returns non-<!-- open: 470, close: 469 --><font class="lisp">nil</font><!-- open: 470, close: 470 --> <!-- MATCHED MATCHED MATCHED -->.  The function's name
means "remove if this condition is true".
</div>

<div class='defun' id='rem-if-not'>
  <font class='exdent'>
    <font class='funcname'>rem-if-not </font>
    <font class='italic' color='purple'>predicate list</font>
  </font><br>
<!-- open: 471, close: 470 --><font class="italic">predicate</font><!-- open: 471, close: 471 --> <!-- MATCHED MATCHED MATCHED --> should be a function of one argument.
<!-- open: 472, close: 471 --><font class="lisp">rem-if-not</font><!-- open: 472, close: 472 --> <!-- MATCHED MATCHED MATCHED --> makes a new list by applying <!-- open: 473, close: 472 --><font class="italic">predicate</font><!-- open: 473, close: 473 --> <!-- MATCHED MATCHED MATCHED --> to
all of the elements of <!-- open: 474, close: 473 --><font class="italic">list</font><!-- open: 474, close: 474 --> <!-- MATCHED MATCHED MATCHED --> and removing the ones for which the predicate 
returns <!-- open: 475, close: 474 --><font class="lisp">nil</font><!-- open: 475, close: 475 --> <!-- MATCHED MATCHED MATCHED -->.  The function's name
means "remove if this condition is not true"; i.e. it keeps the elements
for which <!-- open: 476, close: 475 --><font class="italic">predicate</font><!-- open: 476, close: 476 --> <!-- MATCHED MATCHED MATCHED --> is true.
</div>

<div class='defun' id='del-if'>
  <font class='exdent'>
    <font class='funcname'>del-if </font>
    <font class='italic' color='purple'>predicate list</font>
  </font><br>
<!-- open: 477, close: 476 --><font class="lisp">del-if</font><!-- open: 477, close: 477 --> <!-- MATCHED MATCHED MATCHED --> is just like <!-- open: 478, close: 477 --><font class="lisp">rem-if</font><!-- open: 478, close: 478 --> <!-- MATCHED MATCHED MATCHED --> except that it modifies <!-- open: 479, close: 478 --><font class="italic">list</font><!-- open: 479, close: 479 --> <!-- MATCHED MATCHED MATCHED -->
rather than creating a new list.  See <!-- open: 480, close: 479 --><font class="lisp">rem-if</font><!-- open: 480, close: 480 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='del-if-not'>
  <font class='exdent'>
    <font class='funcname'>del-if-not </font>
    <font class='italic' color='purple'>predicate list</font>
  </font><br>
<!-- open: 481, close: 480 --><font class="lisp">del-if-not</font><!-- open: 481, close: 481 --> <!-- MATCHED MATCHED MATCHED --> is just like <!-- open: 482, close: 481 --><font class="lisp">rem-if-not</font><!-- open: 482, close: 482 --> <!-- MATCHED MATCHED MATCHED --> except that it modifies <!-- open: 483, close: 482 --><font class="italic">list</font><!-- open: 483, close: 483 --> <!-- MATCHED MATCHED MATCHED -->
rather than creating a new list.  See <!-- open: 484, close: 483 --><font class="lisp">rem-if-not</font><!-- open: 484, close: 484 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='every'>
  <font class='exdent'>
    <font class='funcname'>every </font>
    <font class='italic' color='purple'>list predicate &optional step-function</font>
  </font><br>
<!-- open: 485, close: 484 --><font class="lisp">every</font><!-- open: 485, close: 485 --> <!-- MATCHED MATCHED MATCHED --> returns <!-- open: 486, close: 485 --><font class="lisp">t</font><!-- open: 486, close: 486 --> <!-- MATCHED MATCHED MATCHED --> if <!-- open: 487, close: 486 --><font class="italic">predicate</font><!-- open: 487, close: 487 --> <!-- MATCHED MATCHED MATCHED --> returns
non-<!-- open: 488, close: 487 --><font class="lisp">nil</font><!-- open: 488, close: 488 --> <!-- MATCHED MATCHED MATCHED --> when applied to every element of <!-- open: 489, close: 488 --><font class="italic">list</font><!-- open: 489, close: 489 --> <!-- MATCHED MATCHED MATCHED -->,
or <!-- open: 490, close: 489 --><font class="lisp">nil</font><!-- open: 490, close: 490 --> <!-- MATCHED MATCHED MATCHED --> if <!-- open: 491, close: 490 --><font class="italic">predicate</font><!-- open: 491, close: 491 --> <!-- MATCHED MATCHED MATCHED --> returns <!-- open: 492, close: 491 --><font class="lisp">nil</font><!-- open: 492, close: 492 --> <!-- MATCHED MATCHED MATCHED --> for some element.
If <!-- open: 493, close: 492 --><font class="italic">step-function</font><!-- open: 493, close: 493 --> <!-- MATCHED MATCHED MATCHED --> is present, it replaces <!-- open: 494, close: 493 --><font class="lisp">cdr</font><!-- open: 494, close: 494 --> <!-- MATCHED MATCHED MATCHED -->
as the function used to get to the next element of the list.
</div>

<div class='defun' id='some'>
  <font class='exdent'>
    <font class='funcname'>some </font>
    <font class='italic' color='purple'>list predicate &optional step-function</font>
  </font><br>
<!-- open: 495, close: 494 --><font class="lisp">some</font><!-- open: 495, close: 495 --> <!-- MATCHED MATCHED MATCHED --> returns a tail of <!-- open: 496, close: 495 --><font class="italic">list</font><!-- open: 496, close: 496 --> <!-- MATCHED MATCHED MATCHED --> such that the car
of the tail is the first element that the <!-- open: 497, close: 496 --><font class="italic">predicate</font><!-- open: 497, close: 497 --> <!-- MATCHED MATCHED MATCHED --> returns
non-<!-- open: 498, close: 497 --><font class="lisp">nil</font><!-- open: 498, close: 498 --> <!-- MATCHED MATCHED MATCHED --> when applied to,
or <!-- open: 499, close: 498 --><font class="lisp">nil</font><!-- open: 499, close: 499 --> <!-- MATCHED MATCHED MATCHED --> if <!-- open: 500, close: 499 --><font class="italic">predicate</font><!-- open: 500, close: 500 --> <!-- MATCHED MATCHED MATCHED --> returns <!-- open: 501, close: 500 --><font class="lisp">nil</font><!-- open: 501, close: 501 --> <!-- MATCHED MATCHED MATCHED --> for every element.
If <!-- open: 502, close: 501 --><font class="italic">step-function</font><!-- open: 502, close: 502 --> <!-- MATCHED MATCHED MATCHED --> is present, it replaces <!-- open: 503, close: 502 --><font class="lisp">cdr</font><!-- open: 503, close: 503 --> <!-- MATCHED MATCHED MATCHED -->
as the function used to get to the next element of the list.
</div>

<div class='defun' id='tailp'>
  <font class='exdent'>
    <font class='funcname'>tailp </font>
    <font class='italic' color='purple'>sublist list</font>
  </font><br>
Returns <!-- open: 504, close: 503 --><font class="lisp">t</font><!-- open: 504, close: 504 --> <!-- MATCHED MATCHED MATCHED --> if <!-- open: 505, close: 504 --><font class="italic">sublist</font><!-- open: 505, close: 505 --> <!-- MATCHED MATCHED MATCHED --> is a sublist of <!-- open: 506, close: 505 --><font class="italic">list</font><!-- open: 506, close: 506 --> <!-- MATCHED MATCHED MATCHED --> (i.e.
one of the conses that makes up <!-- open: 507, close: 506 --><font class="italic">list</font><!-- open: 507, close: 507 --> <!-- MATCHED MATCHED MATCHED -->).  Otherwise returns <!-- open: 508, close: 507 --><font class="lisp">nil</font><!-- open: 508, close: 508 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='sxhash'>
  <font class='exdent'>
    <font class='funcname'>sxhash </font>
    <font class='italic' color='purple'>S-expression</font>
  </font><br>
<p class='cindent'><!-- "hash table" -->
<!-- open: 509, close: 508 --><font class="lisp">sxhash</font><!-- open: 509, close: 509 --> <!-- MATCHED MATCHED MATCHED --> computes a hash code of an S-expression, and returns it as
a fixnum, which may be positive or negative.  A property of <!-- open: 510, close: 509 --><font class="lisp">sxhash</font><!-- open: 510, close: 510 --> <!-- MATCHED MATCHED MATCHED -->
is that <!-- open: 511, close: 510 --><font class="lisp">(equal <!-- open: 512, close: 510 --><font class="italic">x y</font><!-- open: 512, close: 511 -->)</font><!-- open: 512, close: 512 --> <!-- MATCHED MATCHED MATCHED --> implies <!-- open: 513, close: 512 --><font class="lisp">(= (sxhash <!-- open: 514, close: 512 --><font class="italic">x</font><!-- open: 514, close: 513 -->) (sxhash <!-- open: 515, close: 513 --><font class="italic">y</font><!-- open: 515, close: 514 -->))</font><!-- open: 515, close: 515 --> <!-- MATCHED MATCHED MATCHED -->.  The
number returned by <!-- open: 516, close: 515 --><font class="lisp">sxhash</font><!-- open: 516, close: 516 --> <!-- MATCHED MATCHED MATCHED --> is some possibly large number in the
range allowed by fixnums.  It is guaranteed that: 
.break
1)<u><font color='green'>SAIL</font></u> <!-- open: 517, close: 516 --><font class="lisp">sxhash</font><!-- open: 517, close: 517 --> <!-- MATCHED MATCHED MATCHED --> for a symbol will always be positive.
.break
2)<u><font color='green'>SAIL</font></u> <!-- open: 518, close: 517 --><font class="lisp">sxhash</font><!-- open: 518, close: 518 --> <!-- MATCHED MATCHED MATCHED --> of any particular expression will be constant
in a particular implementation for all time, probably.
.break
3)<u><font color='green'>SAIL</font></u> <!-- open: 519, close: 518 --><font class="lisp">sxhash</font><!-- open: 519, close: 519 --> <!-- MATCHED MATCHED MATCHED --> of any object of type <!-- open: 520, close: 519 --><font class="lisp">random</font><!-- open: 520, close: 520 --> <!-- MATCHED MATCHED MATCHED --> will be zero.
.break
4)<u><font color='green'>SAIL</font></u> <!-- open: 521, close: 520 --><font class="lisp">sxhash</font><!-- open: 521, close: 521 --> <!-- MATCHED MATCHED MATCHED --> of a fixnum will <!-- open: 522, close: 521 --><font class="lisp">=</font><!-- open: 522, close: 522 --> <!-- MATCHED MATCHED MATCHED --> that fixnum.

Here is an example of how to use <!-- open: 523, close: 522 --><font class="lisp">sxhash</font><!-- open: 523, close: 523 --> <!-- MATCHED MATCHED MATCHED --> in maintaining
hash tables of S-expressions:
<pre class='lisp'>
(defun knownp (x)    ;<!-- open: 524, close: 523 --><font class="main">look up x in the table</font><!-- open: 524, close: 524 --> <!-- MATCHED MATCHED MATCHED -->
  (prog (i bkt)
    (setq i (plus 76 (remainder (sxhash x) 77)))	
      ;The remainder should be reasonably randomized between
      ;-76 and 76, thus table size must be &gt; 175 octal.
    (setq bkt (aref table i))
      ;bkt is thus a list of all those expressions that hash
      ;into the same number as does x.
    (return (memq x bkt))))
</pre>

To write an "intern" for S-expressions, one could
<pre class='lisp'>
(defun sintern (x)
  (prog (bkt i tem)
    (setq bkt (aref table
		    (setq i (+ 2n-2 (<u><font color='green'>SAIL</font></u>\ (sxhash x) 2n-1)))))
	;2n-1 and 2n-2 stand for a power of 2 minus one and 
	;minus two respectively.  This is a good choice to 
	;randomize the result of the remainder operation.
    (return (cond ((setq tem (memq x bkt)) 
		   (car tem))
		  (t (aset (cons x bkt) table i)
		     x)))))
</pre>
</div>

<div class='defun' id='assq'>
  <font class='exdent'>
    <font class='funcname'>assq </font>
    <font class='italic' color='purple'>item alist</font>
  </font><br>
<p class='cindent'><!-- "association lists" -->
<!-- open: 525, close: 524 --><font class="lisp">(assq <!-- open: 526, close: 524 --><font class="italic">item alist</font><!-- open: 526, close: 525 -->)</font><!-- open: 526, close: 526 --> <!-- MATCHED MATCHED MATCHED --> looks up <!-- open: 527, close: 526 --><font class="italic">item</font><!-- open: 527, close: 527 --> <!-- MATCHED MATCHED MATCHED --> in the association list
(list of conses) <!-- open: 528, close: 527 --><font class="italic">alist</font><!-- open: 528, close: 528 --> <!-- MATCHED MATCHED MATCHED -->.  The value is the first cons whose <!-- open: 529, close: 528 --><font class="lisp">car</font><!-- open: 529, close: 529 --> <!-- MATCHED MATCHED MATCHED -->
is <!-- open: 530, close: 529 --><font class="lisp">eq</font><!-- open: 530, close: 530 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 531, close: 530 --><font class="italic">x</font><!-- open: 531, close: 531 --> <!-- MATCHED MATCHED MATCHED -->, or <!-- open: 532, close: 531 --><font class="lisp">nil</font><!-- open: 532, close: 532 --> <!-- MATCHED MATCHED MATCHED --> if there is none such. 
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(assq 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
	=&gt;  (r . x)

(assq 'fooo '((foo . bar) (zoo . goo))) =&gt; nil

(assq 'b '((a b c) (b c d) (x y z))) =&gt; (b c d)
</pre>

It is okay to <!-- open: 533, close: 532 --><font class="lisp">rplacd</font><!-- open: 533, close: 533 --> <!-- MATCHED MATCHED MATCHED --> the result of <!-- open: 534, close: 533 --><font class="lisp">assq</font><!-- open: 534, close: 534 --> <!-- MATCHED MATCHED MATCHED --> as long as it is not <!-- open: 535, close: 534 --><font class="lisp">nil</font><!-- open: 535, close: 535 --> <!-- MATCHED MATCHED MATCHED -->,
if your intention is to "update" the "table" that was <!-- open: 536, close: 535 --><font class="lisp">assq</font><!-- open: 536, close: 536 --> <!-- MATCHED MATCHED MATCHED -->'s second argument.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(setq values '((x .  100) (y  . 200) (z .  50)))
(assq 'y values) =&gt; (y . 200)
(rplacd (assq 'y values)  201)
(assq 'y values)  =&gt; (y . 201) <!-- open: 537, close: 536 --><font class="main">now</font><!-- open: 537, close: 537 --> <!-- MATCHED MATCHED MATCHED -->
</pre>

A typical trick is to say
<!-- open: 538, close: 537 --><font class="lisp">(cdr (assq x y))</font><!-- open: 538, close: 538 --> <!-- MATCHED MATCHED MATCHED -->.
Assuming the cdr of <!-- open: 539, close: 538 --><font class="lisp">nil</font><!-- open: 539, close: 539 --> <!-- MATCHED MATCHED MATCHED --> is guaranteed to be <!-- open: 540, close: 539 --><font class="lisp">nil</font><!-- open: 540, close: 540 --> <!-- MATCHED MATCHED MATCHED -->,
this yields <!-- open: 541, close: 540 --><font class="lisp">nil</font><!-- open: 541, close: 541 --> <!-- MATCHED MATCHED MATCHED --> if no pair is found (or if a pair is
found whose cdr is <!-- open: 542, close: 541 --><font class="lisp">nil</font><!-- open: 542, close: 542 --> <!-- MATCHED MATCHED MATCHED -->.)

<!-- open: 543, close: 542 --><font class="lisp">assq</font><!-- open: 543, close: 543 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun assq (item list)
    (cond ((null list) nil)
          ((eq item (caar list)) (car list))
          ((assq item (cdr list))) ))
</pre>
</div>

<div class='defun' id='assoc'>
  <font class='exdent'>
    <font class='funcname'>assoc </font>
    <font class='italic' color='purple'>item alist</font>
  </font><br>
<!-- open: 544, close: 543 --><font class="lisp">assoc</font><!-- open: 544, close: 544 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 545, close: 544 --><font class="lisp">assq</font><!-- open: 545, close: 545 --> <!-- MATCHED MATCHED MATCHED --> except that the comparison uses <!-- open: 546, close: 545 --><font class="lisp">equal</font><!-- open: 546, close: 546 --> <!-- MATCHED MATCHED MATCHED --> instead of <!-- open: 547, close: 546 --><font class="lisp">eq</font><!-- open: 547, close: 547 --> <!-- MATCHED MATCHED MATCHED -->.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(assoc '(a b) '((x . y) ((a b) . 7) ((c . d) .e)))
	=&gt; ((a b) . 7)
</pre>
<!-- open: 548, close: 547 --><font class="lisp">assoc</font><!-- open: 548, close: 548 --> <!-- MATCHED MATCHED MATCHED --> could have been defined by:
<pre class='lisp'>
(defun assoc (item list)
    (cond ((null list) nil)
          ((equal item (caar list)) (car list))
          ((assoc item (cdr list))) ))
</pre>
</div>

<div class='defun' id='ass'>
  <font class='exdent'>
    <font class='funcname'>ass </font>
    <font class='italic' color='purple'>predicate item alist</font>
  </font><br>
<!-- open: 549, close: 548 --><font class="lisp">ass</font><!-- open: 549, close: 549 --> <!-- MATCHED MATCHED MATCHED --> is the same as <!-- open: 550, close: 549 --><font class="lisp">assq</font><!-- open: 550, close: 550 --> <!-- MATCHED MATCHED MATCHED --> except that it takes an extra argument
which should be a predicate of two arguments, which is used for the
comparison instead of <!-- open: 551, close: 550 --><font class="lisp">eq</font><!-- open: 551, close: 551 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 552, close: 551 --><font class="lisp">(ass 'eq a b)</font><!-- open: 552, close: 552 --> <!-- MATCHED MATCHED MATCHED --> is the same as
<!-- open: 553, close: 552 --><font class="lisp">(assq a b)</font><!-- open: 553, close: 553 --> <!-- MATCHED MATCHED MATCHED -->. (c.f. <!-- open: 554, close: 553 --><font class="lisp">mem</font><!-- open: 554, close: 554 --> <!-- MATCHED MATCHED MATCHED --> <font color='red'>LINK:(</font>mem-fun))
</div>

<div class='defun' id='memass'>
  <font class='exdent'>
    <font class='funcname'>memass </font>
    <font class='italic' color='purple'>predicate item alist</font>
  </font><br>
<!-- open: 555, close: 554 --><font class="lisp">memass</font><!-- open: 555, close: 555 --> <!-- MATCHED MATCHED MATCHED --> searches <!-- open: 556, close: 555 --><font class="italic">alist</font><!-- open: 556, close: 556 --> <!-- MATCHED MATCHED MATCHED --> just like <!-- open: 557, close: 556 --><font class="lisp">ass</font><!-- open: 557, close: 557 --> <!-- MATCHED MATCHED MATCHED -->, but returns
the portion of the list beginning with the pair containing <!-- open: 558, close: 557 --><font class="italic">item</font><!-- open: 558, close: 558 --> <!-- MATCHED MATCHED MATCHED -->,
rather than the pair itself.  <!-- open: 559, close: 558 --><font class="lisp">(car (memass <!-- open: 560, close: 558 --><font class="italic">x y z</font><!-- open: 560, close: 559 -->)) =
(ass <!-- open: 561, close: 559 --><font class="italic">x y z</font><!-- open: 561, close: 560 -->)</font><!-- open: 561, close: 561 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='defun' id='rassoc'>
  <font class='exdent'>
    <font class='funcname'>rassoc </font>
    <font class='italic' color='purple'>item alist</font>
  </font><br>
<!-- open: 562, close: 561 --><font class="lisp">rassoc</font><!-- open: 562, close: 562 --> <!-- MATCHED MATCHED MATCHED --> means <!-- open: 563, close: 562 --><font class="italic">reverse assoc</font><!-- open: 563, close: 563 --> <!-- MATCHED MATCHED MATCHED -->.  It is like <!-- open: 564, close: 563 --><font class="lisp">assoc</font><!-- open: 564, close: 564 --> <!-- MATCHED MATCHED MATCHED -->, but
it tries to find an element of <!-- open: 565, close: 564 --><font class="italic">alist</font><!-- open: 565, close: 565 --> <!-- MATCHED MATCHED MATCHED --> whose <!-- open: 566, close: 565 --><font class="italic">cdr</font><!-- open: 566, close: 566 --> <!-- MATCHED MATCHED MATCHED --> (not car)
is <!-- open: 567, close: 566 --><font class="italic">equal</font><!-- open: 567, close: 567 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 568, close: 567 --><font class="italic">item</font><!-- open: 568, close: 568 --> <!-- MATCHED MATCHED MATCHED -->.  <!-- open: 569, close: 568 --><font class="lisp">rassoc</font><!-- open: 569, close: 569 --> <!-- MATCHED MATCHED MATCHED --> is defined by:
<pre class='lisp'>
(defun rassoc (item in-list) 
    (do l in-list (cdr l) (null l) 
      (and (equal item (cdar l)) 
	   (return (car l)))))
</pre>
</div>

<div class='defun' id='sassq'>
  <font class='exdent'>
    <font class='funcname'>sassq </font>
    <font class='italic' color='purple'>item alist fcn</font>
  </font><br>
<!-- open: 570, close: 569 --><font class="lisp">(sassq <!-- open: 571, close: 569 --><font class="italic">item alist fcn</font><!-- open: 571, close: 570 -->)</font><!-- open: 571, close: 571 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 572, close: 571 --><font class="lisp">(assq <!-- open: 573, close: 571 --><font class="italic">item alist</font><!-- open: 573, close: 572 -->)</font><!-- open: 573, close: 573 --> <!-- MATCHED MATCHED MATCHED --> except
that if <!-- open: 574, close: 573 --><font class="italic">item</font><!-- open: 574, close: 574 --> <!-- MATCHED MATCHED MATCHED --> is not found in <!-- open: 575, close: 574 --><font class="italic">alist</font><!-- open: 575, close: 575 --> <!-- MATCHED MATCHED MATCHED -->, instead of returning <!-- open: 576, close: 575 --><font class="lisp">nil</font><!-- open: 576, close: 576 --> <!-- MATCHED MATCHED MATCHED -->,
<!-- open: 577, close: 576 --><font class="lisp">sassq</font><!-- open: 577, close: 577 --> <!-- MATCHED MATCHED MATCHED --> calls the function <!-- open: 578, close: 577 --><font class="italic">fcn</font><!-- open: 578, close: 578 --> <!-- MATCHED MATCHED MATCHED --> with no arguments.  <!-- open: 579, close: 578 --><font class="lisp">sassq</font><!-- open: 579, close: 579 --> <!-- MATCHED MATCHED MATCHED --> could
have been defined by: 
<pre class='lisp'>
(defun sassq (item alist fcn)
    (or (assq item alist)
        (apply fcn nil)))
</pre>

<!-- open: 580, close: 579 --><font class="lisp">sassq</font><!-- open: 580, close: 580 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 581, close: 580 --><font class="lisp">sassoc</font><!-- open: 581, close: 581 --> <!-- MATCHED MATCHED MATCHED --> (see below) are of limited use.
These are primarily leftovers from Lisp 1.5.
</div>

<div class='defun' id='sassoc'>
  <font class='exdent'>
    <font class='funcname'>sassoc </font>
    <font class='italic' color='purple'>item alist fcn</font>
  </font><br>
<!-- open: 582, close: 581 --><font class="lisp">(sassoc <!-- open: 583, close: 581 --><font class="italic">item alist fcn</font><!-- open: 583, close: 582 -->)</font><!-- open: 583, close: 583 --> <!-- MATCHED MATCHED MATCHED --> is like <!-- open: 584, close: 583 --><font class="lisp">(assoc <!-- open: 585, close: 583 --><font class="italic">item alist</font><!-- open: 585, close: 584 -->)</font><!-- open: 585, close: 585 --> <!-- MATCHED MATCHED MATCHED --> except that if
<!-- open: 586, close: 585 --><font class="italic">item</font><!-- open: 586, close: 586 --> <!-- MATCHED MATCHED MATCHED --> is not found in <!-- open: 587, close: 586 --><font class="italic">alist</font><!-- open: 587, close: 587 --> <!-- MATCHED MATCHED MATCHED -->, instead of returning <!-- open: 588, close: 587 --><font class="lisp">nil</font><!-- open: 588, close: 588 --> <!-- MATCHED MATCHED MATCHED -->, <!-- open: 589, close: 588 --><font class="lisp">sassoc</font><!-- open: 589, close: 589 --> <!-- MATCHED MATCHED MATCHED --> calls
the function <!-- open: 590, close: 589 --><font class="italic">fcn</font><!-- open: 590, close: 590 --> <!-- MATCHED MATCHED MATCHED --> with no arguments.  <!-- open: 591, close: 590 --><font class="lisp">sassoc</font><!-- open: 591, close: 591 --> <!-- MATCHED MATCHED MATCHED --> could have been
defined by: 
<pre class='lisp'>
(defun sassoc (item alist fcn)
    (or (assoc item alist)
        (apply fcn nil)))
</pre>
</div>

<div class='defun' id='pairlis'>
  <font class='exdent'>
    <font class='funcname'>pairlis </font>
    <font class='italic' color='purple'>cars cdrs</font>
  </font><br>
<!-- open: 592, close: 591 --><font class="lisp">pairlis</font><!-- open: 592, close: 592 --> <!-- MATCHED MATCHED MATCHED --> takes two lists and makes an association list which associates
elements of the first list with corresponding elements of the second
list.
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(pairlis '(beef clams kitty) '(roast fried yu-shiang))
   =&gt; ((beef . roast) (clams . fried) (kitty . yu-shiang))
</pre>
</div>

<div class='defun' id='find-position-in-list'>
  <font class='exdent'>
    <font class='funcname'>find-position-in-list </font>
    <font class='italic' color='purple'>item list</font>
  </font><br>
<!-- open: 593, close: 592 --><font class="lisp">find-position-in-list</font><!-- open: 593, close: 593 --> <!-- MATCHED MATCHED MATCHED --> looks down <!-- open: 594, close: 593 --><font class="italic">list</font><!-- open: 594, close: 594 --> <!-- MATCHED MATCHED MATCHED --> for an element which
is <!-- open: 595, close: 594 --><font class="lisp">eq</font><!-- open: 595, close: 595 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 596, close: 595 --><font class="italic">item</font><!-- open: 596, close: 596 --> <!-- MATCHED MATCHED MATCHED -->, like <!-- open: 597, close: 596 --><font class="lisp">memq.</font><!-- open: 597, close: 597 --> <!-- MATCHED MATCHED MATCHED -->  However, it returns the numeric index
in the list at which it found the first occurence of <!-- open: 598, close: 597 --><font class="italic">item</font><!-- open: 598, close: 598 --> <!-- MATCHED MATCHED MATCHED -->, or
<!-- open: 599, close: 598 --><font class="lisp">nil</font><!-- open: 599, close: 599 --> <!-- MATCHED MATCHED MATCHED --> if it did not find it at all.
<pre class='lisp'>
<font class='exdent'>Examples:
</font><!-- exdent -->(find-position-in-list 'a '(a b c)) =&gt; 0
(find-position-in-list 'c '(a b c)) =&gt; 2
(find-position-in-list 'e '(a b c)) =&gt; nil
</pre>
</div>

<div class='defun' id='find-position-in-list-equal'>
  <font class='exdent'>
    <font class='funcname'>find-position-in-list-equal </font>
    <font class='italic' color='purple'>item list</font>
  </font><br>
<!-- open: 600, close: 599 --><font class="lisp">find-position-in-list-equal</font><!-- open: 600, close: 600 --> <!-- MATCHED MATCHED MATCHED --> is exactly the same as
<!-- open: 601, close: 600 --><font class="lisp">find-position-in-list</font><!-- open: 601, close: 601 --> <!-- MATCHED MATCHED MATCHED -->, except that the comparison is done
with <!-- open: 602, close: 601 --><font class="lisp">equal</font><!-- open: 602, close: 602 --> <!-- MATCHED MATCHED MATCHED --> instead of <!-- open: 603, close: 602 --><font class="lisp">eq</font><!-- open: 603, close: 603 --> <!-- MATCHED MATCHED MATCHED -->.
</div>

<div class='section' id='7.6'>7.6 Tables</div><p class='cindent' id='alist'><!-- Property list -->

[The stuff in FD.SYM will get moved here, leaving a pointer behind, and
will be generalized for disembodied property lists and made to clarify
the distinction between a plist and a paired list.]

<div class='section' id='7.7'>7.7 Tables</div><p class='cindent'><!-- hash table -->

A hash table is a Lisp object that works something like a property list.
Each hash table has a set of <!-- open: 604, close: 603 --><font class="italic">entries</font><!-- open: 604, close: 604 --> <!-- MATCHED MATCHED MATCHED -->, each of which associates a
particular <!-- open: 605, close: 604 --><font class="italic">key</font><!-- open: 605, close: 605 --> <!-- MATCHED MATCHED MATCHED --> with a particular <!-- open: 606, close: 605 --><font class="italic">value</font><!-- open: 606, close: 606 --> <!-- MATCHED MATCHED MATCHED -->.  The basic functions
that deal with hash tables can create entries, delete entries, and find
the value that is associated with a given key.  Finding the value is
very fast even if there are many entries, because hashing is used; this
is an important advantage of hash tables over property lists.

A given hash table can only associate one <!-- open: 607, close: 606 --><font class="italic">value</font><!-- open: 607, close: 607 --> <!-- MATCHED MATCHED MATCHED --> with a given
<!-- open: 608, close: 607 --><font class="italic">key</font><!-- open: 608, close: 608 --> <!-- MATCHED MATCHED MATCHED -->; if you try to add a second <!-- open: 609, close: 608 --><font class="italic">value</font><!-- open: 609, close: 609 --> <!-- MATCHED MATCHED MATCHED --> it will replace the
first.

Hash tables are created with the function <!-- open: 610, close: 609 --><font class="lisp">make-hash-table</font><!-- open: 610, close: 610 --> <!-- MATCHED MATCHED MATCHED -->, which
takes various options.  New entries are added to hash tables with the
<!-- open: 611, close: 610 --><font class="lisp">puthash</font><!-- open: 611, close: 611 --> <!-- MATCHED MATCHED MATCHED --> function.  To look up a key and find the associated value,
the <!-- open: 612, close: 611 --><font class="lisp">gethash</font><!-- open: 612, close: 612 --> <!-- MATCHED MATCHED MATCHED --> function is used.  To remove an entry, use <!-- open: 613, close: 612 --><font class="lisp">remhash</font><!-- open: 613, close: 613 --> <!-- MATCHED MATCHED MATCHED -->.
Here is a simple example.

<pre class='lisp'>
(setq a (make-hash-table))

(puthash 'color 'brown a)

(puthash 'name 'fred a)

(gethash 'color a) =&gt; brown

(gethash 'name a) =&gt; fred
</pre>

In this example, the symbols <!-- open: 614, close: 613 --><font class="lisp">color</font><!-- open: 614, close: 614 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 615, close: 614 --><font class="lisp">name</font><!-- open: 615, close: 615 --> <!-- MATCHED MATCHED MATCHED --> are being used as
keys, and the symbols <!-- open: 616, close: 615 --><font class="lisp">brown</font><!-- open: 616, close: 616 --> <!-- MATCHED MATCHED MATCHED --> and <!-- open: 617, close: 616 --><font class="lisp">fred</font><!-- open: 617, close: 617 --> <!-- MATCHED MATCHED MATCHED --> are being used as the
associated values.  The hash table has two items in it, one of which
associates from <!-- open: 618, close: 617 --><font class="lisp">color</font><!-- open: 618, close: 618 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 619, close: 618 --><font class="lisp">brown</font><!-- open: 619, close: 619 --> <!-- MATCHED MATCHED MATCHED -->, and the other of which
associates from <!-- open: 620, close: 619 --><font class="lisp">name</font><!-- open: 620, close: 620 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 621, close: 620 --><font class="lisp">fred</font><!-- open: 621, close: 621 --> <!-- MATCHED MATCHED MATCHED -->.

Keys do not have to be symbols; they can be any Lisp object.  Likewise
values can be any Lisp object.  The Lisp function <!-- open: 622, close: 621 --><font class="lisp">eq</font><!-- open: 622, close: 622 --> <!-- MATCHED MATCHED MATCHED --> is used to
compare keys, rather than <!-- open: 623, close: 622 --><font class="lisp">equal</font><!-- open: 623, close: 623 --> <!-- MATCHED MATCHED MATCHED -->.  This means that keys are really
objects, but it means that it is not reasonable to use numbers other
than fixnums as keys.  Hash tables are properly interfaced to the
relocating garbage collector so that garbage collection will have no
perceptible effect on the functionality of hash tables.

When a hash table is first created, it has a <!-- open: 624, close: 623 --><font class="italic">size</font><!-- open: 624, close: 624 --> <!-- MATCHED MATCHED MATCHED -->, which is the
maximum number of entries it can hold.  Usually the actual capacity of
the table is somewhat less, since the hashing is not perfectly
collision-free.  With the maximum possible bad luck, the capacity could
be very much less, but this rarely happens.  If so many entries are
added that the capacity is exceeded, the hash table will automatically
grow, and the entries will be <!-- open: 625, close: 624 --><font class="italic">rehashed</font><!-- open: 625, close: 625 --> <!-- MATCHED MATCHED MATCHED --> (new hash values will be
recomputed, and everything will be rearranged so that the fast hash
lookup still works).  This is transparent to the caller; it all happens
automatically.

If the calling program is using multiprocessing, it must be careful to
make sure that there are never two processes both referencing the hash
table at the same time.  There is no locking built into hash tables; if
you have two processes that both want to reference the same hash table,
you must arrange mutual exclusion yourself by using a lock or some other
means.  Don't worry about this if you don't use multiprocessing; but if
you do use multiprocessing, you will have a lot of trouble if you don't
understand this.

<div class='defun' id='make-hash-table'>
  <font class='exdent'>
    <font class='funcname'>make-hash-table </font>
    <font class='italic' color='purple'>&rest options</font>
  </font><br>
This creates a new hash table.  Valid option keywords are:

<table>
<tr valign='top'>
<td><font class='lisp'> :size</font></td><td>Set the initial size of the hash table, in entries, as a fixnum.  The
default is 100 (octal).  The actual size is rounded up from the size
you specify to the next "good" size.
You won't necessarily be able to store this many entries into the table
before it overflows and becomes bigger; but except in the case of extreme
bad luck you will be able to store almost this many.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> :area</font></td><td>Specify the area in which the hash table should be created.  This is
just like the first argument to <!-- open: 626, close: 625 --><font class="lisp">make-array</font><!-- open: 626, close: 626 --> <!-- MATCHED MATCHED MATCHED --> (see <font color='red'>LINK:(</font>make-array-fun)).
Defaults to <!-- open: 627, close: 626 --><font class="lisp">nil</font><!-- open: 627, close: 627 --> <!-- MATCHED MATCHED MATCHED --> (i.e. <!-- open: 628, close: 627 --><font class="lisp">default-cons-area</font><!-- open: 628, close: 628 --> <!-- MATCHED MATCHED MATCHED -->).
</td></tr>
<tr valign='top'><td colspan='2'><font class='lisp'> :rehash-function</font></td><td><!-- empty --></td></tr>
<tr><td><!-- empty title --></td><td>Specify the function to be used for rehashing when the table becomes
full.  Defaults to the internal rehashing function that does the usual
thing.  If you want to write your own rehashing function, you will
have to understand all the internals of how hash tables work.  These
internals are not documented here, as the best way to learn them is
to read the source code.
</td></tr>
<tr valign='top'>
<td><font class='lisp'> :rehash-size</font></td><td>Specifies how much to increase the size of the hash table when it becomes
full.  This can be a fixnum which is the number of entries to add, or
it can be a flonum which is the ratio of the new size to the old size.
The default is <!-- open: 629, close: 628 --><font class="lisp">1.3</font><!-- open: 629, close: 629 --> <!-- MATCHED MATCHED MATCHED -->, which causes the table to be made 30% bigger
each time it has to grow.
</td></tr><!-- item_ --></table><!-- end table -->

</div>

<div class='defun' id='gethash'>
  <font class='exdent'>
    <font class='funcname'>gethash </font>
    <font class='italic' color='purple'>key hash-table</font>
  </font><br>
Find the entry in <!-- open: 630, close: 629 --><font class="italic">hash-table</font><!-- open: 630, close: 630 --> <!-- MATCHED MATCHED MATCHED --> whose key is <!-- open: 631, close: 630 --><font class="italic">key</font><!-- open: 631, close: 631 --> <!-- MATCHED MATCHED MATCHED -->, and return the
associated value.  If there is no such entry, return <!-- open: 632, close: 631 --><font class="lisp">nil</font><!-- open: 632, close: 632 --> <!-- MATCHED MATCHED MATCHED -->.
Returns a second value, which is <!-- open: 633, close: 632 --><font class="lisp">t</font><!-- open: 633, close: 633 --> <!-- MATCHED MATCHED MATCHED --> if an entry was found or <!-- open: 634, close: 633 --><font class="lisp">nil</font><!-- open: 634, close: 634 --> <!-- MATCHED MATCHED MATCHED --> if there
is no entry for <!-- open: 635, close: 634 --><font class="italic">key</font><!-- open: 635, close: 635 --> <!-- MATCHED MATCHED MATCHED --> in this table.
</div>

<div class='defun' id='puthash'>
  <font class='exdent'>
    <font class='funcname'>puthash </font>
    <font class='italic' color='purple'>key value hash-table</font>
  </font><br>
Create an entry associating <!-- open: 636, close: 635 --><font class="italic">key</font><!-- open: 636, close: 636 --> <!-- MATCHED MATCHED MATCHED --> to <!-- open: 637, close: 636 --><font class="italic">value</font><!-- open: 637, close: 637 --> <!-- MATCHED MATCHED MATCHED -->; if there is already an
entry for <!-- open: 638, close: 637 --><font class="italic">key</font><!-- open: 638, close: 638 --> <!-- MATCHED MATCHED MATCHED -->, then replace the value of that entry with <!-- open: 639, close: 638 --><font class="italic">value</font><!-- open: 639, close: 639 --> <!-- MATCHED MATCHED MATCHED -->.
Returns <!-- open: 640, close: 639 --><font class="italic">value</font><!-- open: 640, close: 640 --> <!-- MATCHED MATCHED MATCHED -->. 
</div>

<div class='defun' id='remhash'>
  <font class='exdent'>
    <font class='funcname'>remhash </font>
    <font class='italic' color='purple'>key hash-table</font>
  </font><br>
Remove any entry for <!-- open: 641, close: 640 --><font class="italic">key</font><!-- open: 641, close: 641 --> <!-- MATCHED MATCHED MATCHED --> in <!-- open: 642, close: 641 --><font class="italic">hash-table</font><!-- open: 642, close: 642 --> <!-- MATCHED MATCHED MATCHED -->.  Returns <!-- open: 643, close: 642 --><font class="lisp">t</font><!-- open: 643, close: 643 --> <!-- MATCHED MATCHED MATCHED --> if there was an
entry or <!-- open: 644, close: 643 --><font class="lisp">nil</font><!-- open: 644, close: 644 --> <!-- MATCHED MATCHED MATCHED --> if there was not.
</div>

<div class='defun' id='maphash'>
  <font class='exdent'>
    <font class='funcname'>maphash </font>
    <font class='italic' color='purple'>function hash-table</font>
  </font><br>
For each entry in <!-- open: 645, close: 644 --><font class="italic">hash-table</font><!-- open: 645, close: 645 --> <!-- MATCHED MATCHED MATCHED -->, call <!-- open: 646, close: 645 --><font class="italic">function</font><!-- open: 646, close: 646 --> <!-- MATCHED MATCHED MATCHED --> on two arguments:
the key of the entry and the value of the entry.
</div>

<div class='defun' id='clrhash'>
  <font class='exdent'>
    <font class='funcname'>clrhash </font>
    <font class='italic' color='purple'>hash-table</font>
  </font><br>
Remove all the entries from <!-- open: 647, close: 646 --><font class="italic">hash-table</font><!-- open: 647, close: 647 --> <!-- MATCHED MATCHED MATCHED -->.  Returns the hash table itself.
</div>

The <!-- open: 648, close: 647 --><font class="lisp">describe</font><!-- open: 648, close: 648 --> <!-- MATCHED MATCHED MATCHED --> function (see <font color='red'>LINK:(</font>describe-fun)) prints a variety of
useful information when applied to a hash table.

This hash table facility is similar to the hasharray facility of Interlisp,
and some of the function names are the same.  However, it is <!-- open: 649, close: 648 --><font class="italic">not</font><!-- open: 649, close: 649 --> <!-- MATCHED MATCHED MATCHED --> compatible.
The exact details and the order of arguments are designed to be consistent
with the rest of the Lisp machine rather than with Interlisp.  For instance,
the order of arguments to <!-- open: 650, close: 649 --><font class="lisp">maphash</font><!-- open: 650, close: 650 --> <!-- MATCHED MATCHED MATCHED --> is different, we do not have the Interlisp
"system hash table", and we do not have the
Interlisp restriction that keys and values may not be <!-- open: 651, close: 650 --><font class="lisp">nil</font><!-- open: 651, close: 651 --> <!-- MATCHED MATCHED MATCHED -->.  


<div class='section' id='7.8'>7.8 Sorting</div><p class='cindent'><!-- "sorting" -->

Several functions are provided for sorting arrays and lists.  These
functions use algorithms which always terminate no matter what sorting
predicate is used, provided only that the predicate always terminates. 
The array sort is not necessarily <!-- open: 652, close: 651 --><font class="italic">stable</font><!-- open: 652, close: 652 --> <!-- MATCHED MATCHED MATCHED -->; that is, equal items may
not stay in their original order.  However the list sort <!-- open: 653, close: 652 --><font class="italic">is</font><!-- open: 653, close: 653 --> <!-- MATCHED MATCHED MATCHED -->
stable. 

After sorting, the argument (be it list or array) is rearranged
internally so as to be completely ordered.  In the case of an array
argument, this is accomplished by permuting the elements of the array,
while in the list case, the list is reordered by <!-- open: 654, close: 653 --><font class="lisp">rplacd</font><!-- open: 654, close: 654 --> <!-- MATCHED MATCHED MATCHED -->'s in the
same manner as <!-- open: 655, close: 654 --><font class="lisp">nreverse</font><!-- open: 655, close: 655 --> <!-- MATCHED MATCHED MATCHED -->.  Thus if the argument should not be
clobbered, the user must sort a copy of the argument, obtainable by
<!-- open: 656, close: 655 --><font class="lisp">fillarray</font><!-- open: 656, close: 656 --> <!-- MATCHED MATCHED MATCHED --> or <!-- open: 657, close: 656 --><font class="lisp">append</font><!-- open: 657, close: 657 --> <!-- MATCHED MATCHED MATCHED -->, as appropriate. 

Should the comparison predicate cause an error, such as a wrong type
argument error, the state of the list or array being sorted is
undefined.  However, if the error is corrected the sort will, of
course, proceed correctly. 

The sorting package is smart about cdr-coded lists.

<div class='defun' id='sort'>
  <font class='exdent'>
    <font class='funcname'>sort </font>
    <font class='italic' color='purple'>table predicate</font>
  </font><br>
The first argument to <!-- open: 658, close: 657 --><font class="lisp">sort</font><!-- open: 658, close: 658 --> <!-- MATCHED MATCHED MATCHED --> is an array or a list.  The second
is a predicate, which must be applicable to
all the objects in the array or list.  The predicate should take two
arguments, and return non-<!-- open: 659, close: 658 --><font class="lisp">nil</font><!-- open: 659, close: 659 --> <!-- MATCHED MATCHED MATCHED --> if and only if the first argument is
strictly less than the second (in some appropriate sense). 
<!-- Sorting works on n-bit arrays and so on, right? -->

The <!-- open: 660, close: 659 --><font class="lisp">sort</font><!-- open: 660, close: 660 --> <!-- MATCHED MATCHED MATCHED --> function proceeds to sort the contents of the array or
list under the ordering imposed by the predicate, and returns the
array or list modified into sorted order, i.e. its modified first
argument.  Note that since sorting requires many comparisons, and thus
many calls to the predicate, sorting will be much faster if the
predicate is a compiled function rather than interpreted. 
<pre class='lisp'>
<font class='exdent'>Example:
</font><!-- exdent -->(defun mostcar (x)
    (cond ((symbolp x) x)
          ((mostcar (car x)))))

(sort 'fooarray
      (function (lambda (x y)
	  (alphalessp (mostcar x) (mostcar y)))))
</pre>
If <!-- open: 661, close: 660 --><font class="lisp">fooarray</font><!-- open: 661, close: 661 --> <!-- MATCHED MATCHED MATCHED --> contained these items before the sort:
<pre class='lisp'>
(Tokens (The lion sleeps tonight))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
</pre>
then after the sort <!-- open: 662, close: 661 --><font class="lisp">fooarray</font><!-- open: 662, close: 662 --> <!-- MATCHED MATCHED MATCHED --> would contain:
<pre class='lisp'>
((Beach Boys) (I get around))
(Beatles (I want to hold your hand))
(Carpenters (Close to you))
((Rolling Stones) (Brown sugar))
(Tokens (The lion sleeps tonight))
</pre>
</div>

<div class='defun' id='sortcar'>
  <font class='exdent'>
    <font class='funcname'>sortcar </font>
    <font class='italic' color='purple'>x predicate</font>
  </font><br>
<!-- open: 663, close: 662 --><font class="lisp">sortcar</font><!-- open: 663, close: 663 --> <!-- MATCHED MATCHED MATCHED --> is exactly like <!-- open: 664, close: 663 --><font class="lisp">sort</font><!-- open: 664, close: 664 --> <!-- MATCHED MATCHED MATCHED -->, but the items in the array or
list being sorted should all be conses.  <!-- open: 665, close: 664 --><font class="lisp">sortcar</font><!-- open: 665, close: 665 --> <!-- MATCHED MATCHED MATCHED --> takes the
<!-- open: 666, close: 665 --><font class="lisp">car</font><!-- open: 666, close: 666 --> <!-- MATCHED MATCHED MATCHED --> of each item before handing two items to the predicate.  Thus
<!-- open: 667, close: 666 --><font class="lisp">sortcar</font><!-- open: 667, close: 667 --> <!-- MATCHED MATCHED MATCHED --> is to <!-- open: 668, close: 667 --><font class="lisp">sort</font><!-- open: 668, close: 668 --> <!-- MATCHED MATCHED MATCHED --> as <!-- open: 669, close: 668 --><font class="lisp">mapcar</font><!-- open: 669, close: 669 --> <!-- MATCHED MATCHED MATCHED --> is to <!-- open: 670, close: 669 --><font class="lisp">maplist</font><!-- open: 670, close: 670 --> <!-- MATCHED MATCHED MATCHED -->. 
</div>

The spelling of the names of the next two functions will be corrected at some point.

<div class='defun' id='sort-grouped-array'>
  <font class='exdent'>
    <font class='funcname'>sort-grouped-array </font>
    <font class='italic' color='purple'>array group-size predicate</font>
  </font><br>
<!-- open: 671, close: 670 --><font class="lisp">sorted-array</font><!-- open: 671, close: 671 --> <!-- MATCHED MATCHED MATCHED --> considers its array argument to
be composed of records of -size</font><!-- open: 671, close: 672 --> elements each.
These records are considered as units, and are sorted with respect
to one another.  The <!-- open: 672, close: 672 --><font class="italic">predicate</font><!-- open: 672, close: 673 --> is applied to the first element
of each record; so the first elements act as the keys on which
the records are sorted.
</div>

<div class='defun' id='sort-grouped-array-group-key'>
  <font class='exdent'>
    <font class='funcname'>sort-grouped-array-group-key </font>
    <font class='italic' color='purple'>array group-size predicate</font>
  </font><br>
This is like <!-- open: 673, close: 673 --><font class="lisp">sorted-array</font><!-- open: 673, close: 674 --> except that the
<!-- open: 674, close: 674 --><font class="italic">predicate</font><!-- open: 674, close: 675 --> is applied to four arguments:  an array,
an index into that array, a second array, and an index into
the second array.  <!-- open: 675, close: 675 --><font class="italic">predicate</font><!-- open: 675, close: 676 --> should consider each index
as a subscript of the first element of a record in the corresponding
array, and compare the two records.  This is more general
than <!-- open: 676, close: 676 --><font class="lisp">sorted-array</font><!-- open: 676, close: 677 --> since the function can get at
all of the elements of the relevant records, instead of only the first element.
</div>
<!-- eof -->
</body>
</html>

